У профессора Икс есть массив из n чисел. Он делает q запросов. Каждый запрос состоит из двух целых чисел l и r. Ответом на запрос является сумма чисел с индексами от l до r в исходном массиве.
Уровень счастья профессора Икс будет равен суммарному значению всех ответов на запросы.
Логан хочет сделать профессора Икс максимально счастливым. С этой целью он может изменить порядок элементов в массиве произвольным образом.
К сожалению, у него совсем не получается это сделать и он обратился за помощью к вам.
Ваша задача — посчитать максимально возможное значения уровня счастья профессора Икс, если можно изменить порядок элементов в массиве произвольным образом.
В первой строке входного файла находятся два целых числа n и q (1 ≤ n, q ≤ 105).
Во второй строке находится n целых чисел ai задающих элементы массива (1 ≤ ai ≤ 108).
В последующих q строках находятся пары чисел l и r (1 ≤ l ≤ r ≤ n) обозначающие границы отрезка на котором нужно посчитать сумму элементов.
В единственной строке выходного файла выведите единственное целое число - максимально возможный уровень счастья профессора Икс, если можно изменить порядок элементов в массиве произвольным образом.
3 4
7 3 1
1 3
2 3
3 3
2 2
31
Первая группа тестов состоит из тестов, для которых выполняется ограничение n, q ≤ 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 30 баллов.
Вторая группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 70 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Запросить информацию о проверке» на вкладке «Решения».