Problembeskrivning

Herr JOI äger $N$ träd på sin tomt. Dessa träd står i en rad och är numrerade i ordning med heltal från $1$ till $N$.

Denna vinter har herr JOI bestämt sig för att välja ut några träd och dekorera dem med julbelysning. För julbelysningen finns ett värde som kallas skönhet. Skönheten när man dekorerar träd $i$ med julbelysning är $A_i$.

Herr JOI lade märke till att om han dekorerar båda av $2$ träd som står för nära varandra med julbelysning, kan det bli alltför bländande. Mer specifikt visade det sig att för $j = 1, 2, \dots, M$ bör han inte dekorera $2$ eller fler träd bland träden $L_j$, $L_j + 1$, $\dots$, $R_j$ med julbelysning.

Bestäm det största möjliga värdet på den totala skönheten när träden dekoreras med julbelysning enligt detta villkor.

Begränsningar

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

Indata / Utdata

Indata
Indatan ges från standardindata i följande format:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Utdata
Skriv på $1$ rad ut det största möjliga värdet på julbelysningens totala skönhet.

Deluppgifter

1. ($10$ poäng) $N \le 16$, $M \le 16$
2. ($30$ poäng) $N \le 300$, $M \le 300$
3. ($30$ poäng) $N \le 4000$, $M \le 4000$
4. ($30$ poäng) Inga ytterligare begränsningar.

Exempel på indata / utdata

Exempelindata 1

4 1
1 2 3 8
2 4

Exempelutdata 1

9

I detta exempel blir den totala skönheten $9$ om man dekorerar träden $1$, $4$ med julbelysning, vilket är det maximala värdet. Eftersom $L_1 = 2$, $R_1 = 4$ kan man inte dekorera $2$ eller fler träd bland träden $2$, $3$, $4$. Observera att man till exempel inte kan dekorera träden $1$, $2$, $4$.

Exempelindata 2

5 2
2 3 9 5 6
1 3
2 4

Exempelutdata 2

15

Exempelindata 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

Exempelutdata 3

4912419478