## BOI 2006 P2 - Coin Collector

View as PDF

Points: 7
Time limit: 10.0s
Memory limit: 512M

Problem types

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:

1. Let the amount of change to give be cents.
2. Find the highest denomination that does not exceed . (Let it be the -cent coin.)
3. Give the customer a -cent coin and reduce by .

The coin collector buys one item, paying with his -cent bill.

• 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?

#### Input

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, .

#### Output

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.

#### Sample Input

7 25
1 0
2 0
3 1
5 0
10 0
13 0
20 0

#### Sample Output

3
6