Maximum query sum

You are given an array of $n$ numbers and $q$ queries $(l_i, r_i)$. The answer to a query is $a_{l_i} + \ldots + a_{r_i}$. Before the queries the elements may be rearranged in any way. Find the maximum total of the answers to all queries.

The first line contains $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$). The second line contains integers (). Each of the next lines contains a query: two integers and ().

A single number — the maximum total.

Let $f_i$ be the number of queries that cover position $i$; a difference array gives it in $O(n + q)$. The total is $\sum$, so the largest number goes to the most used position: sort and separately and multiply matching elements.