Монокарп снова играет в компьютерную игру. Он ученик мага, поэтому знает только одно заклинание. К счастью, это заклинание может наносить урон монстрам.
Уровень, на котором он сейчас, содержит \(n\) монстров. \(i\)-й из них появляется через \(k_i\) секунд с начала уровня и имеет \(h_i\) очков здоровья. Дополнительно есть ограничение \(h_i \le k_i\) для всех \(1 \le i \le n\). Все \(k_i\) различны.
Монокарп может использовать заклинание в моменты времени, которые являются положительным целым количеством секунд с начала уровня: \(1, 2, 3, \dots\) Урон от заклинания считается следующим образом. Если он не использовал заклинание в предыдущую секунду, то урон равен \(1\). Иначе, пусть урон в прошлую секунду был равен \(x\). Тогда он может выбрать, чтобы урон был либо \(x + 1\), либо \(1\). Заклинание использует ману: использование заклинания с уроном \(x\) использует \(x\) маны. Мана не восстанавливается.
Чтобы убить \(i\)-го монстра, Монокарп должен использовать заклинание с уроном хотя бы \(h_i\) ровно в тот момент, когда появляется монстр, что равно \(k_i\).
Обратите внимание, что Монокарп может использовать заклинание и тогда, когда в текущую секунду монстра нет.
Количество маны, необходимое для использования всех заклинаний, — это сумма маны по всем использованным заклинаниям. Посчитайте наименьшее количество маны, которое потребуется Монокарпу, чтобы убить всех монстров.
Можно показать, что всегда можно убить всех монстров в рамках ограничений задачи.
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее количество маны, которое потребуется Монокарпу, чтобы убить всех монстров.
Примечание
В первом наборе входных данных Монокарп может использовать заклинание через \(3, 4, 5\) и \(6\) секунд с начала уровня с уроном \(1, 2, 3\) и \(4\), соответственно. Урон в \(6\) секунду равен \(4\), что действительно больше или равно здоровью монстра, который появляется.
Во втором наборе входных данных Монокарп может использовать заклинание через \(3, 4\) и \(5\) секунд с начала уровня с уроном \(1, 2\) и \(3\), соответственно.
В третьем наборе входных данных Монокарп может использовать заклинание через \(4, 5, 7, 8\) и \(9\) секунд с начала уровня с уроном \(1, 2, 1, 1\) и \(2\), соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2
|
10
6
7
|