28830번 - Сила волшебных заклинаний 다국어

문제

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

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

Бой длится $m$ минут. Дамблдор не так прост и подготовил свои сильные заклинания. На $i$-й минуте он может применить заклинание и убить магов с номерами $a,ドル $a + 1,ドル \dots, $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,ドル \dots, $s_n$. $s_i$ означает силу $i$-го мага ($|s_i| \le 10^9$).

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

출력

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

제한

힌트