Ông JOI có \(N\) cây trong khuôn viên nhà mình. Các cây nằm trên một hàng và được đánh số từ \(1\) đến \(N\) theo thứ tự.

Mùa đông này, ông quyết định chọn một số cây để trang trí đèn. Việc trang trí đèn cho cây \(i\) mang lại độ đẹp bằng \(A_i\).

Ông JOI nhận thấy rằng trang trí đèn cho cả hai cây quá gần nhau có thể gây chói mắt. Cụ thể, với mỗi \(j=1,2,\ldots,M\), trong các cây \(L_j,L_j+1,\ldots,R_j\), không được trang trí đèn cho từ hai cây trở lên.

Hãy tìm tổng độ đẹp lớn nhất có thể đạt được khi tuân thủ tất cả các điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N M
A_1 A_2 ... A_N
L_1 R_1
L_2 R_2
...
L_M R_M

Dữ liệu ra

In ra một dòng chứa tổng độ đẹp lớn nhất có thể đạt được.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N \le 2\times 10^5\).
• \(1 \le M \le 2\times 10^5\).
• \(1 \le A_i \le 10^9\) với \(1 \le i \le N\).
• \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).

Phân nhóm

1. Nhóm 1 (10 điểm): \(1 \le N,M \le 16\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
2. Nhóm 2 (30 điểm): \(1 \le N,M \le 300\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
3. Nhóm 3 (30 điểm): \(1 \le N,M \le 4000\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
4. Nhóm 4 (30 điểm): \(1 \le N,M \le 2\times 10^5\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).

Ví dụ

4 1
1 2 3 8
2 4

9

5 2
2 3 9 5 6
1 3
2 4

15

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

4912419478

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.