Cho mảng ~a~ gồm ~n~ số nguyên dương và ~q~ đoạn chỉ số ~[l_i, r_i]~. Trước khi tính các truy vấn, bạn được phép hoán vị các phần tử của mảng tùy ý. Sau đó, giá trị của truy vấn thứ ~i~ là tổng các phần tử tại các vị trí từ ~l_i~ đến ~r_i~.

Hãy tìm tổng lớn nhất có thể của giá trị cả ~q~ truy vấn.

Input

• Dòng đầu gồm hai số nguyên ~n~ và ~q~, lần lượt là số phần tử và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~.
• Trong ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~l_i~ và ~r_i~, mô tả đoạn chỉ số đóng ~[l_i, r_i]~.

Output

• In một số nguyên là tổng lớn nhất có thể sau khi sắp xếp lại mảng.

Giới hạn

• ~1 ≤ n ≤ 2 × 10^5~.
• ~1 ≤ q ≤ 2 × 10^5~.
• ~1 ≤ a_i ≤ 2 × 10^5~ với mọi ~1 ≤ i ≤ n~.
• ~1 ≤ l_i ≤ r_i ≤ n~ với mọi ~1 ≤ i ≤ q~.

Ví dụ

Input

3 3
5 3 2
1 2
2 3
1 3

Output

25

Giải thích ví dụ

Vị trí 2 xuất hiện trong cả ba truy vấn, còn vị trí 1 và 3 đều xuất hiện hai lần. Đặt giá trị lớn nhất 5 vào vị trí 2 và hai giá trị còn lại vào hai vị trí kia, ta thu được tổng 5 × 3 + 3 × 2 + 2 × 2 = 25.