28999번 - Логан и запросы 다국어

문제

У профессора Икс есть массив из $n$ чисел. Он делает $q$ запросов. Каждый запрос состоит из двух целых чисел $l$ и $r$. Ответом на запрос является сумма чисел с индексами от $l$ до $r$ в исходном массиве.

Уровень счастья профессора Икс будет равен суммарному значению всех ответов на запросы.

Логан хочет сделать профессора Икс максимально счастливым. С этой целью он может изменить порядок элементов в массиве произвольным образом.

К сожалению, у него совсем не получается это сделать и он обратился за помощью к вам.

Ваша задача --- посчитать максимально возможное значения уровня счастья профессора Икс, если можно изменить порядок элементов в массиве произвольным образом.

입력

В первой строке входного файла находятся два целых числа $n$ и $q$ $(1 \leq n, q \leq 10^5)$.

Во второй строке находится $n$ целых чисел $a_i$ задающих элементы массива $(1 \leq a_i \leq 10^8)$.

В последующих $q$ строках находятся пары чисел $l$ и $r$ $(1 \leq l \leq r \leq n)$ обозначающие границы отрезка на котором нужно посчитать сумму элементов.

출력

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

제한

힌트