题目描述

在一个国家，有 $N$ 种面额的硬币在流通，包括 $1$ 分硬币。此外，还有一种面值 $K$ 分的纸币，其价值超过了任何一种硬币。有个硬币收藏家想收集每种面额的硬币标本。他家里已经有几枚硬币了，但目前他的钱包里只有一张 $K$ 分的纸币。他在一家商店里，那里的商品都以低于 $K$ 分的所有价格出售（$1$ 分，$2$ 分，$3$ 分，$\cdots$，$K-1$ 分）。在这家商店，零钱是按照以下算法找零的：

1. 让零钱的数额是 $A$ 分。
2. 找到不超过 $A$ 的最高面额(让它是 $B$ 分硬币)。
3. 给顾客一枚 $B$ 分硬币，把 $A$ 减去 $B$。
4. 如果 $A=0$ ，结束；否则返回步骤 $2$。

硬币收藏家用 $K$ 分买了一件东西。
你的任务是编写一个程序来确定:

• 有多少种不同的硬币，收藏家在他的之前的收藏中没有而可以通过此次交易获得?
• 在这个过程中，商店能卖给他的最贵的东西是什么?

输入格式

第一行包含整数 $N$ 和 $K$。接下来的 $N$ 行描述流通中的货币。第 $i+1$ 行包含整数 $c_i$ 和 $d_i$，$c_i$ 表示硬币的面额（分），$d_i$ 为 $1$ 表示该收藏家已有该面额硬币，为 $0$ 表示还无。硬币按价值递增的顺序排列，即：$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

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 \le N \le 5×10^5$，$2 \le K \le 10^9$，$1 \le c_i \le K$。

题目说明

来源于 Baltic Olympiad in Informatics 2006 的 Day 1:Coins。
由 @求学的企鹅 翻译整理。