Coin Collector

In a certain country, N denominations of coins are in circulation, and the smallest one is the 1-cent coin. There is also a bill worth K cents whose value is larger than every coin. A coin collector wants to own one specimen of each denomination. He already has some of the coins at home, and right now he is carrying a single K-cent bill.

He is in a shop that sells items at every price from 1 to K-1 cents. When giving change, the shop uses the following algorithm:

1. Let A be the amount of change still to be returned.
2. Find the largest denomination that does not exceed A; call it the B-cent coin.
3. Give the customer one B-cent coin and decrease A by B.
4. If A = 0, stop; otherwise go back to step 2.

The collector buys exactly one item and pays with his K-cent bill. Determine:

• the maximum number of distinct denominations he does not yet own that he can obtain from the change of this single purchase, and
• the highest possible price of the item he buys such that the change still contains that maximum number of new denominations.

The first line contains two integers N (1 ≤ N ≤ 500000) and K (2 ≤ K ≤ 1000000000). Each of the next N lines describes one denomination: the (i+1)-th line contains two integers c_i (1 ≤ c_i < K) and d_i, where c_i is the coin's value in cents and d_i is 1 if the collector already owns this coin or 0 if he does not. The coins are listed in strictly increasing order of value (c_1 < c_2 < ... < c_N), and the first coin is the 1-cent coin (c_1 = 1).

Print two lines. The first line contains one integer: the maximum number of denominations the collector does not yet own but can acquire with a single purchase. The second line contains one integer: the highest price of an item to buy so that the change returned contains that maximum number of new denominations.