Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

G. Молочные дни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Что сделано, то сделано, и испорченное молоко не исправить.

Маленький Джон настолько мал, насколько ночь — это день, он был известен как гигант, возможно, ростом $$$2.1$$$ метра. Это связано с его любовью к молоку.

В его молочном дневнике $$$n$$$ записей, показывающих, что он приобрел $$$a_i$$$ пинт свежего молока в день $$$d_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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество дней молочного насыщения.

Пример
Входные данные
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
Выходные данные
3
3
4
5
10
6
Примечание

В первом наборе входных данных $$$5$$$ пинт молока хороши в течение $$$3$$$ дней до порчи.

Во втором наборе входных данных произойдёт следующее:

  • в день $$$1$$$ он получит $$$5$$$ пинт молока и выпьет $$$3$$$ из них (останется $$$2$$$ пинты с дня $$$1$$$);
  • в день $$$2$$$ он получит $$$7$$$ пинт молока и выпьет $$$3$$$ из них (останется $$$2$$$ пинты с дня $$$1$$$ и $$$4$$$ пинты с дня $$$2$$$);
  • в день $$$3$$$ он выпьет $$$3$$$ пинты с дня $$$2$$$ (останется $$$2$$$ пинты с дня $$$1$$$ и $$$1$$$ пинта с дня $$$2$$$);
  • в день $$$4$$$ молоко приобретённое в день $$$1$$$ испортится и он выпьет $$$1$$$ пинту с дня $$$2$$$ (больше молока не осталось).