Cô bé An rất thích những bài toán liên quan đến truy vấn mảng.

Một ngày nọ, cô gặp một bài toán khá nổi tiếng: bạn có một mảng gồm ~n~ phần tử (các phần tử được đánh số từ ~1~). Ngoài ra, có ~q~ truy vấn; mỗi truy vấn được mô tả bởi một cặp số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.

Với mỗi truy vấn, bạn cần tìm tổng các phần tử của mảng trong đoạn chỉ số từ ~l_i~ đến ~r_i~ (bao gồm cả hai đầu).

Tuy nhiên, cô bé cảm thấy bài toán này hơi nhàm chán. Cô quyết định thay đổi thứ tự các phần tử trong mảng trước khi trả lời các truy vấn sao cho tổng của tất cả các kết quả truy vấn là lớn nhất có thể.

Nhiệm vụ của bạn là tính giá trị lớn nhất có thể của tổng các kết quả truy vấn sau khi sắp xếp lại mảng một cách tối ưu.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n \le 2 \cdot 10^5, \ 1 \le q \le 2 \cdot 10^5)~ — số phần tử của mảng và số truy vấn.

Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 2 \cdot 10^5)~ — các phần tử của mảng.

Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~ — truy vấn thứ ~i~.

Output

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

Scoring

Sample Input 1

3 3
5 3 2
1 2
2 3
1 3

Sample Output 1

25

Sample Input 2

5 3
5 2 4 1 3
1 5
2 3
2 3

Sample Output 2

33

Notes

Với Test đầu tiên

Ta có thể sắp xếp lại mảng thành ~[2,5,3]~

Khi đó, truy vấn đầu tiên sẽ cho ra kết quả là ~2+5=7~.

Truy vấn thứ hai cho ra kết quả là ~5+3=8~.

Truy vấn thứ ba cho ra kết quả là ~2+5+3=10~.

Kết quả sẽ bằng ~7+8+10=25~.

Có thể chứng minh được là không có phương án nào khác cho ra kết quả lớn hơn.