Mô tả bài toán

Ông JOI sở hữu $N$ cái cây trong khuôn viên nhà mình. Những cái cây này xếp thành một hàng và được đánh số lần lượt bằng các số nguyên từ $1$ đến $N$.

Mùa đông năm nay, ông JOI quyết định chọn một số cây để gắn đèn trang trí. Đèn trang trí có một giá trị gọi là vẻ đẹp. Vẻ đẹp khi gắn đèn trang trí lên cây $i$ là $A_i$.

Ông JOI nhận ra rằng nếu gắn đèn trang trí lên cả $2$ cây ở quá gần nhau thì có thể sẽ quá chói mắt. Cụ thể là với mỗi $j = 1, 2, \dots, M$, không được gắn đèn trang trí cho từ $2$ cây trở lên trong số các cây $L_j$, $L_j + 1$, $\dots$, $R_j$.

Hãy tìm giá trị lớn nhất của tổng vẻ đẹp khi gắn đèn trang trí tuân theo điều kiện này.

Ràng buộc

• $1 \le N \le 200000 (= 2 \times 10^5)$
• $1 \le M \le 200000 (= 2 \times 10^5)$
• $1 \le A_i \le 1000000000 (= 10^9)$ ($1 \le i \le N$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le M$)

Dữ liệu vào và Kết quả

Dữ liệu vào
Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Kết quả
In ra trên $1$ dòng giá trị lớn nhất của tổng vẻ đẹp của đèn trang trí.

Subtask

1. ($10$ điểm) $N \le 16$, $M \le 16$
2. ($30$ điểm) $N \le 300$, $M \le 300$
3. ($30$ điểm) $N \le 4000$, $M \le 4000$
4. ($30$ điểm) Không có giới hạn bổ sung.

Ví dụ

Đầu vào mẫu 1

4 1
1 2 3 8
2 4

Đầu ra mẫu 1

9

Trong ví dụ này, nếu gắn đèn trang trí lên cây $1$, $4$ thì tổng vẻ đẹp là $9$ và đạt giá trị lớn nhất. Vì $L_1 = 2$, $R_1 = 4$ nên không thể gắn đèn trang trí cho từ $2$ cây trở lên trong số các cây $2$, $3$, $4$. Lưu ý rằng, chẳng hạn, không thể gắn đèn trang trí cho các cây $1$, $2$, $4$.

Đầu vào mẫu 2

5 2
2 3 9 5 6
1 3
2 4

Đầu ra mẫu 2

15

Đầu vào mẫu 3

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

Đầu ra mẫu 3

4912419478