Public Judge

pjudge

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21793. 【NOIP Round #6】重生

统计

猫有九条命,但你有 114514 条命。

题目描述

你有 $n$ 个任务需要完成,第 $i$ 个任务需要 $t_i$ 天。但人的寿命有限,你只剩下 $c$ 天了。

磨刀不误砍柴工,你可以花 $1$ 天时间对第 $i$ 个任务进行深入思考,那么它所需的时间会减少 $d_i$ 天。特别的,如果时间被减为零或负数,这个任务就能被瞬间完成。但人的灵感有限,在一次生命里每个任务只能被深入思考一次。

你可以复活,每次复活会再给你带来 $c$ 天。之前的深入思考的结果会一直保留,不会因复活而消失。

求出你最少需要复活多少次,才能在最后一条命把所有任务都完成。你可以认为在最后一条命之前你并不能做任务,只能对任务进行思考,而在最后一条命既可以思考也可以做任务。

输入格式

第一行一个正整数 $T$ ,表示数据组数。每组数据的格式如下:

  • 第一行两个正整数 $n,c$ ,表示任务的个数,以及一条命的长度。
  • 接下来 $n$ 行,每行两个正整数 $t_i,d_i$ ,描述一个任务。

输出格式

对每组数据,输出一行一个非负整数,表示最少需要复活多少次。

样例 $1$

input

2
3 5
17 5
5 2
15 4
2 1345
1344 1
10 10

output

3
0

explanation

对于第一组数据:

在前三条命,分别把每个任务都深入思考一次,那么任务所需的时间就分别降为 $2,0,3$ 。

在最后一条命,对任务 $1$ 和任务 $3$ 进行深入思考,然后瞬间完成所有任务。

共用四条命,复活三次。可以证明不存在复活次数小于 $3$ 的方案。

对于第二组数据:

先对第二个任务深入思考,然后瞬间完成第二个任务,然后在接下来的 $1344$ 天里完成第一个任务。

样例 $2$

input

1
3 1
1000000000 1
1000000000 1
1000000000 1

output

2999999999

样例 $3\sim6$

见下发文件中的 ex_rebirth*.in/ex_rebirth*.ans ,它们分别对应第 $2\sim 5$ 个子任务。

数据范围

本题采用捆绑测试,你需要通过一个子任务的所有测试点才能得到子任务的分数。

对于所有数据,$1\le T\le 1000, 1\le \sum n\le 2\times 10^5, 1\le c\le 10^9, 1\le d_i\le t_i\le 10^9$ 。

子任务编号 特殊性质 分值
$1$ $\sum n,\sum t_i\le 7$ $10$
$2$ $n,t_i\le 30, T\le 100$ $20$
$3$ $\sum n\le 3000$ $20$
$4$ $c\ge n$ $20$
$5$ $ $ $30$