C. Девочка и максимальная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Девочка очень любит задачи про запросы на массиве.

Однажды ей попалась довольно известная задача: дан массив из $$$n$$$ элементов (элементы массива проиндексированы от 1); также есть $$$q$$$ запросов, каждый из которых задается парой целых чисел $$$l_i$$$, $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$. Для каждого запроса необходимо найти сумму всех элементов массива с индексами от $$$l_i$$$ до $$$r_i$$$ включительно.

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

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

Первая строка содержит два целых числа $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) и $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$), разделенных пробелом — количество элементов в массиве и количество запросов, соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 2\cdot10^5$$$), разделенных пробелами — элементы массива.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), разделенных пробелом — $$$i$$$-й запрос.

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

В единственной строке выведите целое число — максимальную сумму ответов на запросы после перемешивания элементов массива.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3 3
5 3 2
1 2
2 3
1 3
Выходные данные
25
Входные данные
5 3
5 2 4 1 3
1 5
2 3
2 3
Выходные данные
33