Сила волшебных заклинаний
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Уже через пару часов случится легендарный бой между Дамблдором и Грин-де-Вальдом.

Хотя итог боя уже определен, Грин-де-Вальд не собирается сдаваться просто так. Он созвал на помощь $$$n$$$ магов, пронумерованных от $$$1$$$ до $$$n$$$, каждый из которых обладает силой $$$s_i$$$. Обратите внимание, что среди магов могли оказаться сторонники Дамблдора, поэтому $$$s_i$$$ может быть меньше нуля.

Бой длится $$$m$$$ минут. Дамблдор не так прост и подготовил свои сильные заклинания. На $$$i$$$-й минуте он может применить заклинание и убить магов с номерами $$$a$$$, $$$a + 1$$$, ..., $$$b$$$, если $$$l_i \leq a \leq b \leq r_i$$$. Обратите внимание, что Дамблдор может никого не убивать в текущую минуту. После того как Дамблдор выполнит заклинание, он получает урон, равный сумме сил магов, которые остались в живых.

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

Входные данные

В первой строке входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ — количество магов и длительность боя в минутах ($$$1 \leq n \leq 300\,000, 1 \leq m \leq 4$$$).

Во второй строке содержится $$$n$$$ целых чисел $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$. $$$s_i$$$ означает силу $$$i$$$-го мага ($$$|s_i| \le 10^9$$$).

В следующих $$$m$$$ строках содержится по два целых числа $$$l_i$$$ и $$$r_i$$$ — номера магов, между которыми Дамблдор может применять заклинание ($$$1 \leq l_i \leq r_i \leq n$$$).

Выходные данные

В единственной строке выведите целое число — минимальное количество урона, которое мог получить Дамблдор.

Пример

Входные данные
5 2
-1 -2 0 1 2
3 5
1 5
Выходные данные
-6