Tổng truy vấn lớn nhất

Cho một mảng $a$ gồm $n$ phần tử (các phần tử được đánh chỉ số từ $1$) và $q$ truy vấn. Truy vấn thứ $i$ là một cặp số nguyên $l_i,r_i$, yêu cầu tính tổng các phần tử của mảng có chỉ số từ $l_i$ đến $r_i$.

Trước khi trả lời các truy vấn, bạn được phép sắp xếp lại mảng $a$ theo một thứ tự bất kỳ (tức là hoán vị các phần tử). Thứ tự này được chọn một lần và dùng chung cho tất cả các truy vấn. Danh sách truy vấn không thay đổi.

Hãy tìm tổng lớn nhất có thể của các câu trả lời cho $q$ truy vấn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$: số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: các phần tử của mảng.
• $q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$ mô tả truy vấn thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng lớn nhất có thể của các câu trả lời sau khi sắp xếp lại mảng một cách tối ưu.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le q\le 2·{10}^5$
• $1\le a_i\le 2·{10}^5$
• $1\le l_i\le r_i\le n$

Ví dụ