Problembeschreibung

Herr JOI besitzt auf seinem Hausgrundstück $N$ Bäume. Diese Bäume stehen in einer Reihe und sind der Reihe nach mit ganzen Zahlen von $1$ bis $N$ nummeriert.

In diesem Winter hat Herr JOI beschlossen, einige Bäume auszuwählen und sie mit einer Lichterkette (Festbeleuchtung) zu schmücken. Für die Beleuchtung ist ein Wert namens Schönheit festgelegt. Die Schönheit beim Schmücken von Baum $i$ beträgt $A_i$.

Herr JOI hat bemerkt, dass es zu grell sein kann, wenn er $2$ zu nahe beieinander stehende Bäume beide beleuchtet. Genauer gesagt hat sich herausgestellt, dass für $j = 1, 2, \dots, M$ unter den Bäumen $L_j$, $L_j + 1$, $\dots$, $R_j$ nicht $2$ oder mehr Bäume beleuchtet werden dürfen.

Bestimme den maximal möglichen Gesamtwert der Schönheit, wenn die Bäume unter Einhaltung dieser Bedingung beleuchtet werden.

Einschränkungen

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

Eingabe / Ausgabe

Eingabe
Die Eingabe erfolgt über die Standardeingabe im folgenden Format:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Ausgabe
Gib den maximal möglichen Gesamtwert der Schönheit der Beleuchtung in $1$ Zeile aus.

Teilaufgaben

1. ($10$ Punkte) $N \le 16$, $M \le 16$
2. ($30$ Punkte) $N \le 300$, $M \le 300$
3. ($30$ Punkte) $N \le 4000$, $M \le 4000$
4. ($30$ Punkte) Keine zusätzlichen Einschränkungen.

Ein- und Ausgabebeispiele

Beispieleingabe 1

4 1
1 2 3 8
2 4

Beispielausgabe 1

9

Wenn in diesem Eingabebeispiel die Bäume $1$, $4$ beleuchtet werden, beträgt die Summe der Schönheit $9$ und ist damit maximal. Da $L_1 = 2$, $R_1 = 4$ gilt, dürfen unter den Bäumen $2$, $3$, $4$ nicht $2$ oder mehr Bäume beleuchtet werden. Beachte, dass zum Beispiel nicht die Bäume $1$, $2$, $4$ beleuchtet werden dürfen.

Beispieleingabe 2

5 2
2 3 9 5 6
1 3
2 4

Beispielausgabe 2

15

Beispieleingabe 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

Beispielausgabe 3

4912419478