[Baltic2006]Coin

某个国家流通着 $N$ 种不同面值的硬币，其中包括面值为 $1$ 分的硬币。此外，还有一种面值为 $K$ 分的纸币，其面值大于所有硬币。

一位硬币收藏家希望收集每一种面值的硬币。他已经拥有其中一些硬币，现在只带着一张面值为 $K$ 分的纸币来到商店。

商店共有 $K-1$ 种商品，价格分别为 $1$ 分、$2$ 分，直至 $K-1$ 分。商店按照以下贪心算法找零：

1. 设当前需要找零 $A$ 分；
2. 找到面值不超过 $A$ 的最大硬币，设其面值为 $B$ 分；
3. 找给顾客一枚面值为 $B$ 分的硬币，并令 $A\gets A-B$；
4. 若 $A=0$，则找零结束；否则返回步骤 $2$。

收藏家想用这张面值为 $K$ 分的纸币购买一件商品。请计算：

• 他最多能够通过找零获得多少种自己尚未拥有的硬币；
• 在获得上述最多种类的新硬币的前提下，他能够购买的最贵商品的价格。

输入格式

第一行包含两个整数 $N$ 和 $K$。

接下来 $N$ 行描述流通的硬币。第 $i$ 行包含两个整数 $c_i$ 和 $a_i$，其中 $c_i$ 表示第 $i$ 种硬币的面值：

• 若 $a_i=1$，表示收藏家已经拥有这种面值的硬币；
• 若 $a_i=0$，表示收藏家尚未拥有这种面值的硬币。

所有 $c_i$ 两两不同，并保证其中包含面值为 $1$ 的硬币。

输出格式

第一行输出一个整数，表示收藏家最多能够获得多少种自己尚未拥有的硬币。

第二行输出一个整数，表示在获得最多种类的新硬币的前提下，他能够购买的最贵商品的价格。

样例输入

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

样例输出

3
6

数据范围

• $1\le N\le 5\times 10^5$；
• $2\le K\le 10^9$；
• $1\le c_i<K$；
• $a_i\in\{0,1\}$；
• 所有 $c_i$ 两两不同，且至少存在一种面值为 $1$ 的硬币。

来源与许可

本题为 Baltic 2006 试题「Coin」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

3
6