Задача . F. Реалистичный геймплей

Недавно вам попался на глаза новый шутер. Говорят, данный шутер обладает реалистичными игровыми механиками.

У вашего персонажа есть пистолет с магазином в \(k\) патронов и ему нужно уничтожить \(n\) волн монстров. Волна \(i\) состоит из \(a_i\) монстров и происходит с момента времени \(l_i\) по момент \(r_i\). Все \(a_i\) появляются в момент \(l_i\) и вы должны уничтожить их всех вплоть до момента \(r_i\) (вы можете убивать монстров ровно в момент \(r_i\)). Для каждой пары последовательных волн верно, что вторая волна начинается не раньше того момента, в который заканчивается первая волна — формально, выполняется условие \(r_i \le l_{i + 1}\). Прочтите примечания к примерам из условия для более хорошего понимания процесса.

Вы уверены в своих навыках и навыках своего персонажа, а потому можете считать, что прицеливание и стрельба моментальны и что вам нужен ровно один выстрел, чтобы убить одного монстра. Однако перезарядка пистолета занимает ровно \(1\) единицу времени.

Одна из реалистичных механик — это механика перезарядки: когда вы перезаряжаетесь, вы выбрасываете старый магазин вместе с оставшимися патронами. А потому постоянные перезарядки могут привести к трате огромного количества патронов.

Вам понравилась данная механика, и вам стало интересно: какое наименьшее количество патронов необходимо потратить (используя или выбрасывая), чтобы уничтожить все волны.

Заметим, что вы не выбрасываете патроны, оставшиеся после уничтожения всех волн монстров, а также начинаете игру с полным магазином.