Есептің шарты

JOI мырзаның өз үйінің аумағында $N$ ағашы бар. Бұл ағаштар бір қатарға тізіліп өсіп тұр және ретімен $1$-ден $N$-ге дейінгі бүтін сандармен нөмірленген.

Осы қыста JOI мырза бірнеше ағашты таңдап, оларды иллюминациямен (жарық шамдармен) безендіруді ұйғарды. Иллюминация үшін әдемілік деп аталатын мән белгіленген. $i$-ші ағашты иллюминациямен безендірген кездегі әдемілік $A_i$-ге тең.

JOI мырза бір-біріне тым жақын орналасқан $2$ ағаштың екеуін де иллюминациямен безендірсе, жарық тым көз қарықтырарлық болуы мүмкін екенін байқады. Нақтырақ айтқанда, $j = 1, 2, \dots, M$ үшін $L_j$, $L_j + 1$, $\dots$, $R_j$ ағаштарының ішінен $2$ немесе одан көп ағашты иллюминациямен безендіруге болмайтыны белгілі болды.

Осы шартқа сәйкес иллюминациямен безендірген кездегі әдеміліктер қосындысының ең үлкен мәнін табыңыз.

Шектеулер

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

Кіріс және шығыс

Кіріс
Кіріс деректер стандартты кірістен келесі форматта беріледі:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Шығыс
Иллюминация әдеміліктері қосындысының ең үлкен мәнін $1$ жолда шығарыңыз.

Ішкі есептер

1. ($10$ ұпай) $N \le 16$, $M \le 16$
2. ($30$ ұпай) $N \le 300$, $M \le 300$
3. ($30$ ұпай) $N \le 4000$, $M \le 4000$
4. ($30$ ұпай) Қосымша шектеулер жоқ.

Кіріс және шығыс мысалдары

Кіріс мысалы 1

4 1
1 2 3 8
2 4

Шығыс мысалы 1

9

Бұл кіріс мысалында $1$, $4$ ағаштарын иллюминациямен безендірсек, әдеміліктер қосындысы $9$ болып, ең үлкен мәнге жетеді. $L_1 = 2$, $R_1 = 4$ болғандықтан, $2$, $3$, $4$ ағаштарының ішінен $2$ немесе одан көп ағашты иллюминациямен безендіруге болмайды. Мысалы, $1$, $2$, $4$ ағаштарын безендіруге болмайтынына назар аударыңыз.

Кіріс мысалы 2

5 2
2 3 9 5 6
1 3
2 4

Шығыс мысалы 2

15

Кіріс мысалы 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

Шығыс мысалы 3

4912419478