Фермер Джон купил новый амбар, содержащий N (1 <= N <= 40,000) доильных машин, последовательно пронумерованных от 1 до N и расположенных в ряд.
Доильная машина i способна извлекать по M(i) (1 <=M(i) <= 100,000) единиц молока в день. Однако, они установлены так близко, что, если машина I используется в какой-то день, то в этот день не могут быть использованы две соседние машины (начальная и конечная машина имеют по одному соседу). ФД может выбирать различные подмножества работающих машин в различные дни.
ФД хочет вычислить максимальное количество молока, которое он может извлечь за серию из D(1 <= D <= 50,000) дней. В начале каждого дня у него есть достаточное количество времени, чтобы выполнить модификацию одной выбранной машины I, и изменить дневной выпуск молока этой машины от прошлого дня к сегодняшнему. Вам дан список этих ежедневных модификаций, определите, сколько молока может извлечь ФД в течение D дней (заметим, что это число может не вместиться в 32-битное целое).
PROBLEM NAME: optmilk
Формат входных данных
* Строка 1: Значения N и D.
* Строки 2..1+N: Строка i+1 содержит начальное значение M(i).
* Строки 2+N..1+N+D: Строка 1+N+d содержит два целых числа i и m, означающие, что ФД изменил значение M(i) на m в начале дня d.
Формат выходных данных
* Строка 1: Максимальное суммарное количество молока, которое ФД сможет произвести за D дней.
Примечание
В день 1 оптимальное количество молока 2+4 = 6 (также достижимое как 1+3+2). В день 2 оптимальное количество молока 7+4=11. В день 3 оптимальное количество молока 10+3+2=15.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1
2
3
4
5
5 2
2 7
1 10
|
32
|