Descrizione del problema

Il signor JOI possiede $N$ alberi nel terreno della sua casa. Questi alberi sono disposti in fila e sono numerati in ordine con gli interi da $1$ a $N$.

Quest'inverno il signor JOI ha deciso di scegliere alcuni alberi e decorarli con delle luminarie. Per le luminarie è definito un valore chiamato bellezza. La bellezza ottenuta decorando l'albero $i$ con le luminarie è $A_i$.

Il signor JOI si è accorto che decorare con le luminarie entrambi di $2$ alberi troppo vicini tra loro potrebbe risultare troppo abbagliante. Nello specifico, per $j = 1, 2, \dots, M$, è emerso che non si devono decorare con le luminarie $2$ o più alberi tra gli alberi $L_j$, $L_j + 1$, $\dots$, $R_j$.

Trova il valore massimo della bellezza totale decorando gli alberi con le luminarie secondo questa condizione.

Vincoli

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

Input / Output

Input
L'input è fornito dallo standard input nel seguente formato:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Output
Stampa su $1$ riga il valore massimo della bellezza totale delle luminarie.

Sottoproblemi

1. ($10$ punti) $N \le 16$, $M \le 16$
2. ($30$ punti) $N \le 300$, $M \le 300$
3. ($30$ punti) $N \le 4000$, $M \le 4000$
4. ($30$ punti) Nessun vincolo aggiuntivo.

Esempi di input / output

Input di esempio 1

4 1
1 2 3 8
2 4

Output di esempio 1

9

In questo esempio di input, decorando con le luminarie gli alberi $1$, $4$, la bellezza totale diventa $9$, che è il massimo. Poiché $L_1 = 2$, $R_1 = 4$, non è possibile decorare $2$ o più alberi tra gli alberi $2$, $3$, $4$. Nota che, ad esempio, non è possibile decorare gli alberi $1$, $2$, $4$.

Input di esempio 2

5 2
2 3 9 5 6
1 3
2 4

Output di esempio 2

15

Input di esempio 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

Output di esempio 3

4912419478