Что сделано, то сделано, и испорченное молоко не исправить.
Маленький Джон настолько мал, насколько ночь — это день, он был известен как гигант, возможно, ростом \(2.1\) метра. Это связано с его любовью к молоку.
В его молочном дневнике \(n\) записей, показывающих, что он приобрел \(a_i\) пинт свежего молока в день \(d_i\). Молоко теряет свежесть с течением времени и остается пригодным для питья максимум \(k\) дней. Другими словами, свежее молоко, приобретенное в день \(d_i\), будет пригодно для питья с дня \(d_i\) по день \(d_i+k-1\) включительно.
Каждый день маленький Джон пьет пригодное для питья молоко, максимум \(m\) пинт. Другими словами, если молока меньше \(m\) пинт, он выпьет все и не будет насыщен; если молока \(m\) пинт или больше, он выпьет ровно \(m\) пинт и будет насыщен, и это будет день молочного насыщения.
Маленький Джон всегда сначала пьет самое свежее пригодное для питья молоко.
Определите количество дней молочного насыщения маленького Джона.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество дней молочного насыщения.
Примечание
В первом наборе входных данных \(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\) (больше молока не осталось).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
3
4
5
10
6
|