Baltic OI '06 P2 - Coin Collector - Olympiads Online Judge

Baltic OI '06 P2 - Coin Collector

View as PDF

Submit solution

All submissions

Best submissions

Points: 12

Time limit: 4.5s

Memory limit: 512M

Problem types

Baltic Olympiad in Informatics: 2006 Day 1, Problem 2

In a certain country, there are $N$ $N$ denominations of coins in circulation, including the $1$ $1$ -cent coin. Additionally, there's a bill whose value of $K$ $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$ $K$ -cent bill in his wallet. He's in a shop where there are items sold at all prices less than $K$ $K$ cents ( $1$ $1$ cent, $2$ $2$ cents, $3$ $3$ cents, $\dots$ $\dots$ , $K - 1$ $K - 1$ cents). In this shop, the change is given using the following algorithm:

Let the amount of change to give be $A$ $A$ cents.
Find the highest denomination that does not exceed $A$ $A$ . (Let it be the $B$ $B$ -cent coin.)
Give the customer a $B$ $B$ -cent coin and reduce $A$ $A$ by $B$ $B$ .
If $A = 0$ $A = 0$ , then end; otherwise return to step $2$ $2$ .

The coin collector buys one item, paying with his $K$ $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?

Input

The first line of the input contains the integers $N$ $N$ $(1 \le N \le 500\,000)$ $(1 \leq N \leq 500 000)$ and $K$ $K$ $(2 \le K \le 1\,000\,000\,000)$ $(2 \leq K \leq 1 000 000 000)$ . The following $N$ $N$ lines describe the coins in circulation. The $(i + 1)$ $(i + 1)$ -th line contains the integers $c_i$ $c_{i}$ $(1 \le c_i < K)$ $(1 \leq c_{i} < K)$ and $d_i$ $d_{i}$ , where $c_i$ $c_{i}$ is the value (in cents) of the coin, and $d_i$ $d_{i}$ is $1$ $1$ , if the collector already has this coin, or $0$ $0$ , if he does not. The coins are given in the increasing order of values, that is, $c_1 < c_2 < \dots < c_N$ $c_{1} < c_{2} < \dots < c_{N}$ . The first coin is known to be the $1$ $1$ -cent coin, that is, $c_1 = 1$ $c_{1} = 1$ .

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

Copy

Sample Output

Copy

3
6

Comments

There are no comments at the moment.