← 返回题目列表

Codeforces · 2014/G

G. 银河日子

中文机器翻译题面 查看原题

小约翰就像黑夜就是白天一样小——众所周知,他是一个巨人,可能有 $$$2.1$$$ 米高。这和他对牛奶的喜爱有很大关系。

他的奶制品日记有 $$$n$$$ 条目,显示他在 $$$d_i$$$ 天购买了 $$$a_i$$$ 品脱鲜牛奶。牛奶的新鲜度会随着时间的推移而下降,最多可饮用 $$$k$$$ 天。换句话说,在$$$d_i$$$日获得的新鲜牛奶将在$$$d_i$$$日和$$$d_i+k-1$$$日之间饮用。

小约翰每天喝可饮用的牛奶,最多 $$$m$$$ 品脱。换句话说,如果牛奶少于 $$$m$$$ 品脱,他会喝完而不满意;如果至少有 $$$m$$$ 品脱牛奶,他会恰好喝 $$$m$$$ 品脱并感到满足,这是牛奶满足日。

小约翰总是先喝最新鲜的饮用牛奶。

确定小约翰的牛奶满意度天数。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^4$$$),即测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$k$$$ ($$$1\le n$$$、$$$m$$$、$$$k \le 10^5$$$)、日记条目数、牛奶满意日所需的最大品脱以及牛奶的新鲜度。

然后跟踪每个测试用例的 $$$n$$$ 行,每行有两个整数 $$$d_i$$$ 和 $$$a_i$$$ ($$$1\le d_i$$$, $$$a_i \le 10^6$$$)、获取牛奶的日期和获取的品脱数量。它们按 $$$d_i$$$ 的递增值排序,并且 $$$d_i$$$ 的所有值都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,即牛奶满意天数。

示例

输入 #1

6
1 1 3
1 5
2 3 3
1 5
2 7
4 5 2
1 9
2 6
4 9
5 6
5 2 4
4 7
5 3
7 1
11 2
12 1
4 1 3
5 10
9 4
14 8
15 3
5 5 5
8 9
10 7
16 10
21 5
28 9

输出 #1

3
3
4
5
10
6

注意

在第一个测试案例中,$$$5$$$ 品脱牛奶在变质之前可以保存 $$$3$$$ 天。

在第二个测试用例中,将发生以下情况:

- 在$$$1$$$日,他将收到$$$5$$$品脱牛奶并喝掉$$$3$$$其中(从$$$1$$$日起留下$$$2$$$品脱);
- 在$$$2$$$那天,他将收到$$$7$$$品脱牛奶并喝掉$$$3$$$其中(从$$$1$$$那天留下$$$2$$$品脱,从$$$2$$$那天留下$$$4$$$品脱);
- 在$$$3$$$日,他将从$$$2$$$日起喝$$$3$$$品脱(留下$$$1$$$日起的$$$2$$$品脱和$$$2$$$日起的$$$1$$$品脱);
- 在$$$4$$$日,$$$1$$$日获得的牛奶将会变质,他将从$$$2$$$日起喝$$$1$$$品脱(不再剩下牛奶)。