Một khu du lịch sinh thái tổ chức chuỗi sự kiện trải nghiệm kéo dài ~n~ ngày. Mỗi ngày ở khu du lịch sẽ có một hoạt động đặc sắc mang lại sự hài lòng lớn cho du khách. Theo kế hoạch, Ban quản lý dự kiến tổ chức đúng ~n~ hoạt động, mỗi hoạt động diễn ra trong đúng 1 ngày và không có ngày nào có 2 hoạt động cùng diễn ra. Theo tính toán, hoạt động thứ ~i~ có độ hấp dẫn là ~a_i~ ~(1 \le i \le n)~.

Có ~m~ đoàn khách đã đăng ký, đoàn thứ ~j~ ~(1 \le j \le m)~ lưu trú từ ngày ~L_j~ đến hết ngày ~R_j~. Để các đoàn khách có trải nghiệm tốt nhất, Ban quản lý quyết định sắp xếp lại thứ tự các hoạt động để có tổng hiệu quả hài lòng của tất cả các đoàn đăng ký là lớn nhất. Biết hiệu quả hài lòng của mỗi đoàn khách là tổng độ hấp dẫn của các hoạt động diễn ra trong thời gian đoàn khách đó lưu trú.

Yêu cầu: Hãy xác định tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ ~(1 \le n, m \le 3 \times 10^5)~.

• Dòng thứ 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^4 \forall i = 1, 2, \dots, n)~.

• Dòng thứ ~j~ trong ~m~ dòng tiếp theo chứa 2 số nguyên ~L_j, R_j~ ~(1 \le L_j \le R_j \le n \forall j = 1, 2, \dots, m)~.

Output

Một số nguyên là tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Scoring

Sample Input 1

3 2
70 30 10
1 2
2 3

Sample Output 1

180

Sample Input 2

3 3
10 70 30
1 3
1 2
1 1

Sample Output 2

280

Notes

• Trong ví dụ 1, ngày 1 tổ chức hoạt động 2, ngày 2 tổ chức hoạt động 1, ngày 3 tổ chức hoạt động 3. Độ hấp dẫn của các hoạt động trong các ngày theo thứ tự là ~[30, 70, 10]~. Hiệu quả hài lòng của đoàn khách thứ nhất là ~30 + 70 = 100~. Hiệu quả hài lòng của đoàn khách thứ hai là ~70 + 10 = 80~.

• Trong ví dụ 2, độ hấp dẫn của các hoạt động trong các ngày theo thứ tự lựa chọn là ~[70, 30, 10]~. Hiệu quả hài lòng của đoàn khách thứ nhất là ~70 + 30 + 10 = 110~. Hiệu quả hài lòng của đoàn khách thứ hai là ~70 + 30 = 100~. Hiệu quả hài lòng của đoàn khách thứ ba là ~70~.