Ограничения: время – 500ms/2500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
> С той стороны частокол заостренный над ним поднимался, -- \
Крепкий, высокий, который воздвигли ахейские мужи,\
Чтобы служил им надежной защитою против троянцев.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Илиада, песнь 12
Ахейцы, высадившиеся под Троей, окружили свой лагерь стеной из `N` последовательных участков разной высоты.
Афина поведала своему любимцу Одиссею, что вскоре на лагерь нападут `M` отрядов троянцев, каждый из которых имеет
численность `K_i` и силу `P_i`. Отряд численностью `K_i` атакует одновременно `K_i` подряд идущих участков стены, и если
суммарная высота этих участков окажется меньше `P_i` -- троянцы прорвутся в лагерь и сожгут ахейские корабли. Но даже
Афина не может заранее предсказать, какие именно участки стены троянцы выберут для атаки. Поэтому Одиссею нужно срочно
надстроить стену так, чтобы избежать поражения ахейцев в любом случае. Суммарная высота надстраиваемых частей
должна быть минимальной, чтобы Одиссей как можно скорее закончил постройку и вернулся к привычным пирам и состязаниям.
В первой строке ввода указаны два целых числа: длина стены `N` (`1<=N<=10^4`) и количество атакующих отрядов `M` (`1<=M<=10^3`).
Следующая строка содержит `N` целых чисел `h_j`: высоты последовательных участков стены (`0<=h_j<=10^9`).
Затем следуют `M` строк, содержащих описания атакующих отрядов, по два целых числа в каждой: численность отряда `K_i` (`1<=K_i<=N`)
и сила отряда `P_i` (`1<=P_i<=10^9`).
Выведите единственное целое число -- минимальную суммарную высоту надстроек.
```sample Пример ввода
5 2
1 4 0 1 1
1 2
2 5
```
```sample Пример вывода
6
```
Пояснение: участки стены после надстройки будут иметь высоты 2, 4, 2, 3, 2.
Соответственно, общая высота надстроек равна 1 + 0 + 2 + 2 + 1 = 6.
Начало
Рабочее место участника
Задачи на идею