На занятиях Дима получил массив из N чисел, на котором он должен сделать Q запросов. Каждый запрос состоит из двух целых чисел L и R. Ответом на запрос служит сумма чисел с индексами от L до R включительно в исходном массиве.

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

Помогите вычислить Диме это значение!

Входные данные Первая строка входного файла INPUT.TXT содержит два целых числа N и Q (1 ≤ N, Q ≤ 10^5).

Во второй строке находится N целых чисел Ai, задающих элементы массива (1 ≤ Ai ≤10^8).

В последующих Q строках находятся пары чисел L и R (1 ≤ L ≤ R ≤ N), обозначающие границы отрезка, на котором нужно вычислять сумму элементов.

Выходные данные В единственной строке выходного файла OUTPUT.TXT выведите единственное целое число – максимально возможную сумму результатов всех запросов, которую Дима может получить.

3 4 7 3 1 1 3 2 3 3 3 2 2

31