Deskripsi Masalah

Tuan JOI memiliki $N$ pohon di halaman rumahnya. Pohon-pohon ini berjajar dalam satu barisan dan diberi nomor secara berurutan dengan bilangan bulat dari $1$ hingga $N$.

Musim dingin ini, Tuan JOI memutuskan untuk memilih beberapa pohon dan menghiasinya dengan lampu hias (iluminasi). Lampu hias memiliki nilai yang disebut keindahan. Keindahan ketika menghiasi pohon $i$ dengan lampu hias adalah $A_i$.

Tuan JOI menyadari bahwa jika ia menghiasi kedua dari $2$ pohon yang terlalu berdekatan dengan lampu hias, cahayanya bisa menjadi terlalu menyilaukan. Secara spesifik, untuk $j = 1, 2, \dots, M$, diketahui bahwa ia tidak boleh menghiasi $2$ pohon atau lebih di antara pohon $L_j$, $L_j + 1$, $\dots$, $R_j$ dengan lampu hias.

Carilah nilai maksimum dari total keindahan ketika menghiasi pohon-pohon tersebut dengan lampu hias sesuai syarat ini.

Batasan

• $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$)

Masukan / Keluaran

Masukan
Masukan diberikan dari Masukan Standar dalam format berikut:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Keluaran
Keluarkan nilai maksimum dari total keindahan lampu hias dalam $1$ baris.

Subsoal

1. ($10$ poin) $N \le 16$, $M \le 16$
2. ($30$ poin) $N \le 300$, $M \le 300$
3. ($30$ poin) $N \le 4000$, $M \le 4000$
4. ($30$ poin) Tidak ada batasan tambahan.

Contoh Masukan / Keluaran

Contoh Masukan 1

4 1
1 2 3 8
2 4

Contoh Keluaran 1

9

Pada contoh masukan ini, jika ia menghiasi pohon $1$, $4$ dengan lampu hias, total keindahannya menjadi $9$, yang merupakan nilai maksimum. Karena $L_1 = 2$, $R_1 = 4$, ia tidak dapat menghiasi $2$ pohon atau lebih di antara pohon $2$, $3$, $4$ dengan lampu hias. Perhatikan bahwa, sebagai contoh, ia tidak dapat menghiasi pohon $1$, $2$, $4$ sekaligus.

Contoh Masukan 2

5 2
2 3 9 5 6
1 3
2 4

Contoh Keluaran 2

15

Contoh Masukan 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

Contoh Keluaran 3

4912419478