Cho một mảng gồm ~n~ phần tử (các phần tử được đánh chỉ số từ 1). Ngoài ra, bạn có ~q~ truy vấn, mỗi truy vấn được xác định bởi một cặp số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~). Với mỗi truy vấn, bạn cần tính tổng các phần tử trong khoảng từ ~l_i~ đến ~r_i~, bao gồm cả hai đầu mút.

Tuy nhiên, bài toán này khá nhàm chán. Ta sắp xếp lại các phần tử của mảng trước khi trả lời truy vấn sao cho tổng các câu trả lời của truy vấn là lớn nhất có thể. Nhiệm vụ của bạn là tìm giá trị tổng lớn nhất này.

Yêu cầu: Tìm giá trị tổng lớn nhất của tất cả 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~ (~1 \le n \le 2 \times 10^5~) và ~q~ (~1 \le q \le 2 \times 10^5~) lần lượt là số lượng phần tử trong mảng và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 2 \times 10^5~) lần lượt là các phần tử của mảng.
• Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ là truy vấn thứ ~i~.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất của tất cả 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.