U136589.[BalticOI 2006] coin collector钱币收藏家（文件判题）

文件读入：coin.in
文件读出：coin.out

有一个国家，流通着 $N$ 种面值的硬币，其中包括了 1 分硬币。另外，有一种面值为 $K$ 分的纸币，它超过了所有硬币的面值。有一位硬币收藏家，他想收集每一种面值的硬币样本。他家里已经有一些硬币，但是现在他只带着一张 $K$ 分纸币去商店。

商店里总共有 $K-1$ 种商品，价格分别为 $1$ 分、$2$ 分…… $K-1$ 分。

这家商店使用以下贪心算法找零：

1. 假设总共需要找 $A$ 分（即 $A = K - \text{商品价格}$）；
2. 寻找最高的不超过 $A$ 的硬币面值，设它为 $B$ 分硬币；
3. 给顾客一枚 $B$ 分硬币，然后令 $A \gets A-B$；
4. 如果 $A=0$，算法结束；否则转第 2 步。

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

1. 收藏家一次购物最多能够得到多少种他【还没有】的硬币？（注意同一种硬币即使找零多枚，也只算作获得 1 种新硬币）。
2. 在满足第一问（获得最多新硬币种类数）的前提下，他能够购买的最贵的商品价格是多少？（即找零金额最小，也就是商品价格最大）。

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

以下 $N$ 行描述各种流通的硬币的面值和是否已收藏状态。第 $i+1$ 行包含整数 $C_i$ 和 $d_i$。

• $C_i$（$1 \le C_i < K$）表示第 $i$ 种硬币的面值。
• 若 $d_i=1$，收藏家已经有硬币 $C_i$；若 $d_i=0$，收藏家还没有硬币 $C_i$。

输入保证按照硬币面值递增顺序，也就是 $C_1 < C_2 < \dots < C_N$，并且第一枚硬币必定是 $1$ 分硬币，也就是 $C_1 = 1$。

输出共两行。

第一行为一个整数，表示收藏家最多能获得多少种之前还没有的硬币。
第二行为一个整数，表示在前一问的前提下，收藏家能购买的最贵的商品价格。

大数据

数据范围

测试点编号	$n$	$K$	特殊性质
$1\sim 4$	$n\le 10^3$	$K\le 10^3$	无
$5\sim 8$	$n\le 5\times 10^4$	$K\le 10^9$	无
$9\sim 14$	$n\le 3\times 10^5$	$K\le 10^9$	无
$15\sim 20$	$n\le 5\times 10^5$	$K\le 10^9$	无

对于所有数据，保证 $1\le n\le 5\times 10^5$，$2\le K\le 10^9$，$C_1=1$，$C_1<C_2<\dots<C_n<K$，$d_i\in\{0,1\}$。