Description du problème

M. JOI possède $N$ arbres sur le terrain de sa maison. Ces arbres sont alignés sur une rangée et sont numérotés dans l'ordre par des entiers de $1$ à $N$.

Cet hiver, M. JOI a décidé de choisir certains arbres et de les décorer avec des illuminations. Une valeur appelée beauté est définie pour les illuminations. La beauté obtenue en décorant l'arbre $i$ avec des illuminations est $A_i$.

M. JOI s'est rendu compte que s'il décore avec des illuminations $2$ arbres trop proches l'un de l'autre, cela risque d'être trop éblouissant. Plus précisément, pour $j = 1, 2, \dots, M$, il s'est avéré qu'il ne faut pas décorer $2$ arbres ou plus parmi les arbres $L_j$, $L_j + 1$, $\dots$, $R_j$.

Trouvez la valeur maximale de la somme des beautés lorsqu'on décore les arbres avec des illuminations en respectant cette condition.

Contraintes

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

Entrée / Sortie

Entrée
L'entrée est fournie depuis l'entrée standard sous le format suivant :
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Sortie
Affichez sur $1$ ligne la valeur maximale de la somme des beautés des illuminations.

Sous-tâches

1. ($10$ points) $N \le 16$, $M \le 16$
2. ($30$ points) $N \le 300$, $M \le 300$
3. ($30$ points) $N \le 4000$, $M \le 4000$
4. ($30$ points) Aucune contrainte supplémentaire.

Exemples d'entrée / sortie

Exemple d'entrée 1

4 1
1 2 3 8
2 4

Exemple de sortie 1

9

Dans cet exemple d'entrée, si l'on décore les arbres $1$, $4$ avec des illuminations, la beauté totale vaut $9$, ce qui est le maximum. Comme $L_1 = 2$, $R_1 = 4$, on ne peut pas décorer $2$ arbres ou plus parmi les arbres $2$, $3$, $4$. Notez par exemple qu'il n'est pas possible de décorer les arbres $1$, $2$, $4$.

Exemple d'entrée 2

5 2
2 3 9 5 6
1 3
2 4

Exemple de sortie 2

15

Exemple d'entrée 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

Exemple de sortie 3

4912419478