题目描述

你需要完成 $n$ 项准备任务，第 $i$ 项任务最初需要 $t_i$ 秒。每轮演练限时 $c$ 秒，你可以任意安排任务的执行顺序，但一次只能执行一项任务，并且必须完成当前任务才能进行其他操作。

你也可以花 $1$ 秒研究某项任务，使这项任务此后所需的执行时间减少 $d_i$ 秒，最少减到 $0$。每轮内，每项任务最多研究一次。 研究和执行任务都消耗本轮时间；可以先研究再执行，最后成功的那一轮也可以研究。耗时为 $0$ 的任务可以立即完成。

若本轮未能完成全部任务，就必须重新开始下一轮。新一轮中，所有任务都要重新执行，但此前研究带来的时间减少永久保留，每项任务也可以再次研究。

求完成全部任务所需的最少重新开始次数。第一轮就成功时，答案为 $0$；恰好在第 $c$ 秒结束时完成，也算成功。

输入格式

第一行包含两个整数 $n,c$，表示任务数和每轮演练的时间限制。

接下来 $n$ 行，第 $i$ 行包含两个整数 $t_i,d_i$，表示第 $i$ 项任务的初始执行时间，以及每次研究可以减少的时间。

输出格式

输出一行一个整数，表示最少需要重新开始的次数。答案可能超过 $32$ 位整数的表示范围。

样例输入 1

3 5
17 5
5 2
15 4

样例输出 1

3

样例 1 解释

前三轮每轮都研究三项任务，剩余执行时间变为 $2,0,3$ 秒，第四轮可在 $5$ 秒内完成。若只重新开始两次，第三轮即使充分研究，仍至少需要 $8$ 秒。因此答案为 $3$。

样例输入 2

2 2
4 4
4 4

样例输出 2

0

样例 2 解释

第一轮分别花 $1$ 秒研究两项任务，将它们的执行时间都降为 $0$，随后立即完成。因此不需要重新开始，答案为 $0$。

数据范围与子任务

对于所有测试数据，保证$1\le n\le2\times10^5$，$1\le c\le10^9$，$1\le d_i\le t_i\le10^9$。子任务 2 中 $U$ 表示使全部任务的耗时降为零所需的研究次数总和。

每个子任务内的正式测试全部通过，才获得该子任务的分数。