题目描述

有一个国家，流通着 $N$ 种面值的硬币，其中包括了 $1$ 分硬币。另外，有一种面值为 $K$ 分的纸币，它超过了所有硬币的面值。

有一位硬币收藏家，他想收集每一种面值的硬币样本。他家里已经有一些硬币，但是现在他只带着一张 $K$ 分纸币去商店。

商店里总共有 $K-1$ 种商品，价格分别为 $1$ 分、$2$ 分、……、$K-1$ 分。这家商店使用以下算法找零：

1. 假设总共需要找 $A$ 分；
2. 寻找最高的不超过 $A$ 的硬币面值，设它为 $B$ 分硬币；
3. 给顾客一枚 $B$ 分硬币，然后令 $A$ 为 $A-B$；
4. 如果 $A=0$，算法结束；否则转到第二步。

收藏家想用他的 $K$ 分纸币买一件商品。请你编写程序，计算：

• 收藏家能够得到多少种他还没有过的硬币？
• 在满足上一问的前提下，他能够买的最贵的商品是什么？

输入格式

第一行为两个整数 $N$（$1\leq N\leq 5\times 10^5$）和 $K$（$2\leq K\leq 10^9$）。

以下 $N$ 行描述流通的硬币。第 $i+1$ 行包含两个整数 $c_i$（$1\leq c_i < k$）和 $d_i$ 表示收藏家是否已经有这枚硬币，若 $d_i=1$ 表示已经拥有，否则表示没有。

输入按照硬币面值递增顺序，也就是 $C_1 < C_2 < \cdots < C_n$，第一枚硬币是 $1$ 分硬币，也就是 $C_1=1$。

输出格式

第一行为一个整数，表示收藏家最多能获得多少种之前还没有的硬币。

第二行为一个整数，表示在前一问的前提下，收藏家能购买的最贵的商品价格。

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

3
6