Descripción del problema

El Sr. JOI posee $N$ árboles en el terreno de su casa. Estos árboles están dispuestos en una fila y están numerados en orden con enteros del $1$ al $N$.

Este invierno, el Sr. JOI decidió elegir algunos árboles y decorarlos con luces navideñas (iluminación). Para la iluminación se define un valor llamado belleza. La belleza al decorar el árbol $i$ con iluminación es $A_i$.

El Sr. JOI notó que si decora con iluminación ambos de $2$ árboles que estén demasiado cerca entre sí, puede resultar demasiado deslumbrante. Específicamente, para $j = 1, 2, \dots, M$, resultó que no debe decorar con iluminación $2$ o más árboles de entre los árboles $L_j$, $L_j + 1$, $\dots$, $R_j$.

Encuentra el valor máximo de la suma de la belleza al decorar los árboles con iluminación de acuerdo con esta condición.

Restricciones

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

Entrada / Salida

Entrada
La entrada se proporciona desde la entrada estándar en el siguiente formato:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Salida
Imprime en $1$ línea el valor máximo de la suma de la belleza de la iluminación.

Subtareas

1. ($10$ puntos) $N \le 16$, $M \le 16$
2. ($30$ puntos) $N \le 300$, $M \le 300$
3. ($30$ puntos) $N \le 4000$, $M \le 4000$
4. ($30$ puntos) Sin restricciones adicionales.

Ejemplo de entrada / salida

Entrada de ejemplo 1

4 1
1 2 3 8
2 4

Salida de ejemplo 1

9

En esta entrada de ejemplo, si se decoran los árboles $1$, $4$ con iluminación, la belleza total es $9$, que es el máximo. Como $L_1 = 2$, $R_1 = 4$, no se pueden decorar $2$ o más árboles de entre los árboles $2$, $3$, $4$. Ten en cuenta que, por ejemplo, no se pueden decorar los árboles $1$, $2$, $4$.

Entrada de ejemplo 2

5 2
2 3 9 5 6
1 3
2 4

Salida de ejemplo 2

15

Entrada de ejemplo 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

Salida de ejemplo 3

4912419478