小约翰就像黑夜就是白天一样小——众所周知,他是一个巨人,可能有 $$$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$$$品脱(不再剩下牛奶)。