Problem Description

In a country, there are $n$ types of coins in circulation, including a 1-cent coin. In addition, there is a banknote of value $K$ cents, which is larger than the value of any coin. A coin collector wants to collect one sample of every coin value. He already has some coins at home, but now he only takes a single $K$-cent banknote to a shop. The shop sells a total of $K-1$ items, priced at $1$ cent, $2$ cents, ..., $K-1$ cents.

The shop gives change using the following algorithm:

1. Suppose the total change needed is $A$ cents.
2. Find the largest coin value not exceeding $A$, and let it be a $B$-cent coin.
3. Give the customer one $B$-cent coin, then set $A$ to $A-B$.
4. If $A=0$, the algorithm ends; otherwise, go to step 2.

The collector wants to buy one item using his $K$-cent banknote. Please write a program to compute: how many types of coins that he does not yet have can the collector obtain? Under the condition of maximizing the previous answer, what is the most expensive item he can buy?

Input Format

The first line contains two integers $n$ and $K$.

The next $n$ lines describe the values of the coins in circulation and whether they have already been collected. Line $i+1$ contains an integer $C_i\ (1\le C_i<K)$ and $d_i$, where $C_i$ is the value of the $i$-th coin. If $d_i=1$, the collector already has coin $C_i$; if $d_i=0$, the collector does not yet have coin $C_i$. The input is given in increasing order of coin values, i.e., $C_1<C_2<\dots<C_n$, and the first coin is the 1-cent coin, i.e., $C_1=1$.

Output Format

The first line outputs one integer, the maximum number of coin types that the collector can obtain that he did not have before.

The second line outputs one integer, under the condition in the previous question, the price of the most expensive item the collector can buy.

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

3
6

Hint

For all data, $1\le n\le 5\times 10^5$, $2\le K\le 10^9$.

Translated by ChatGPT 5