Sắp xếp để tổng lớn nhất

Cho mảng \(a\) gồm \(n\) phần tử (đánh số từ \(1\)) và \(q\) truy vấn; truy vấn thứ \(i\) cho \(l_i \le r_i\) và yêu cầu tính \(a_{l_i} + \ldots + a_{r_i}\).

Trước khi trả lời, ta được hoán vị tùy ý các phần tử của mảng. Hãy chọn thứ tự sao cho tổng của tất cả \(q\) đáp án lớn nhất có thể và in ra giá trị đó.

Input

• Dòng đầu chứa \(n\) và \(q\).
• Dòng hai chứa \(n\) số \(a_1, \ldots, a_n\).
• \(q\) dòng tiếp theo, mỗi dòng chứa \(l_i\) và \(r_i\).

Output

In ra tổng lớn nhất.

Constraints

• \(1 \le n, q \le 2 \cdot 10^5\)
• \(1 \le a_i \le 2 \cdot 10^5\)
• \(1 \le l_i \le r_i \le n\)

Sample Input

4 2
1 4 2 3
1 3
2 4

Sample Output

17

Explanation

Các vị trí \(1,2,3,4\) được phủ \(1,2,2,1\) lần. Xếp \(1,2,3,4\) vào các vị trí phủ ít đến nhiều: \(1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 2 = 17\).