P7638 [BalticOI 2006] COIN COLLECTOR (Day 1)

在一个国家，有 $N$ 种面额的硬币在流通，包括 $1$ 分硬币。此外，还有一种面值 $K$ 分的纸币，其价值超过了任何一种硬币。有个硬币收藏家想收集每种面额的硬币标本。他家里已经有几枚硬币了，但目前他的钱包里只有一张 $K$ 分的纸币。他在一家商店里，那里的商品都以低于 $K$ 分的所有价格出售（$1$ 分，$2$ 分，$3$ 分，$\cdots$，$K-1$ 分）。在这家商店，零钱是按照以下算法找零的： 1. 让零钱的数额是 $A$ 分。 1. 找到不超过 $A$ 的最高面额(让它是 $B$ 分硬币)。 1. 给顾客一枚 $B$ 分硬币，把 $A$ 减去 $B$。 1. 如果 $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$。

第一行包含一个整数，即收集者尚未拥有、但可以通过一次购买获得的最多硬币面额数。第二行包含一个整数，即要购买的商品的最高价格，以便找零包括第一行的新面额的最大数量。

#### 数据规模与约定 对于 $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](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Coins](https://www.cs.helsinki.fi/group/boi2006/tasks/coins.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。