In a certain country, there are denominations of coins in circulation, including the -cent coin. Additionally, there’s a bill whose value of cents is known to exceed any of the coins. There's a coin collector who wants to collect a specimen of each denomination of coins. He already has a few coins at home, but currently he only carries one -cent bill in his wallet. He’s in a shop where there are items sold at all prices less than cents ( cent, cents, cents, , cents). In this shop, the change is given using the following algorithm:
- Let the amount of change to give be cents.
- Find the highest denomination that does not exceed . (Let it be the -cent coin.)
- Give the customer a -cent coin and reduce by .
- If , then end; otherwise return to step .
The coin collector buys one item, paying with his -cent bill.
Your task is to write a program that determines:
- How many different coins that the collector does not yet have in his collection can he acquire with this transaction?
- What is the most expensive item the store can sell him in the process?
The first line of the input contains the integers and . The following lines describe the coins in circulation. The -th line contains the integers and where is the value (in cents) of the coin, and is , if the collector already has this coin, or , if he does not. The coins are given in the increasing order of values, that is, . The first coin is known to be the -cent coin, that is, .
The first line of the output should contain a single integer — the maximal number of denominations that the collector does not yet have, but could acquire with a single purchase. The second line of the output should also contain a single integer — the maximal price of the item to buy so that the change given would include the maximal number of new denominations, as declared on the first line.
7 25 1 0 2 0 3 1 5 0 10 0 13 0 20 0