98 人解决，133 人已尝试。
165 份提交通过，共有 543 份提交。
3.6 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
1-cent coin. Additionally, there’s a bill whose value of K 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 K-cent bill in his wallet. He’s in a shop where there are items sold at all prices less than K cents (1 cent, 2 cents, 3 cents, … , K-1 cents). In this shop, the change is given using the following algorithm:
Let the amount of change to give be A cents.
Find the highest denomination that does not exceed A. (Let it be the B-cent coin.)
Give the customer a B-cent coin and reduce A by B.
If A = 0, then end; otherwise return to step 2.
The coin collector buys one item, paying with his K-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 N (1 <= N <= 500 000) and K (2 <= K <= 1000000000). The following N lines describe the coins in circulation. The (i + 1)-th line contains the integers ci (1 <= ci < K) and di, where ci is the value (in cents) of the coin, and di is 1, if the collector already has this coin, or 0, if he does not. The coins are given in the increasing order of values, that is, c1 < c2 < … < cN. The first coin is known to be the 1-cent coin, that is, c1 = 1.
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 n the first line.
7 25 1 0 2 0 3 1 5 0 10 0 13 0 20 0
3 6
98 人解决，133 人已尝试。
165 份提交通过，共有 543 份提交。
3.6 EMB 奖励。