Наибольшая сумма запросов

Дан массив из $n$ чисел и $q$ запросов $(l_i, r_i)$. Ответ на запрос — $a_{l_i} + \ldots + a_{r_i}$. До запросов элементы массива можно как угодно переставить. Найдите наибольшую сумму ответов на все запросы.

В первой строке $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — $n$ целых чисел ($1 \le a_i \le 2 \cdot 10^5$). В каждой из следующих $q$ строк запрос: два целых числа $l$ и $r$ ($1 \le l \le r \le n$).

Одно число — наибольшая суммарная величина.

Пусть $f_i$ — в скольких запросах участвует позиция $i$; это считается разностным массивом за $O(n + q)$. Сумма равна $\sum f_i \cdot a_{\text{позиция}}$, значит, наибольшее число нужно поставить на самую используемую позицию: отсортируйте $f$ и $a$ отдельно и перемножьте соответствующие элементы.

В первом примере $f = (2, 3, 2)$: $5$ в середину, ответ $5 \cdot 3 + 3 \cdot 2 + 2 \cdot 2 = 25$. Ответ достигает $8 \cdot 10^{15}$ — нужен 64-битный тип.

Источник: Codeforces, задача 276C.