Problem Description

Mr. JOI owns $N$ trees on the grounds of his home. These trees are arranged in a row and are numbered in order with integers from $1$ to $N$.

This winter, Mr. JOI decided to choose some trees and decorate them with illuminations. A value called beauty is defined for the illuminations. The beauty when decorating tree $i$ with illuminations is $A_i$.

Mr. JOI noticed that if he decorates both of $2$ trees that are too close to each other with illuminations, it may be too dazzling. Specifically, for $j = 1, 2, \dots, M$, it turned out that he should not decorate $2$ or more trees among tree $L_j$, $L_j + 1$, $\dots$, $R_j$ with illuminations.

Find the maximum possible total beauty when decorating the trees with illuminations according to this condition.

Constraints

• $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
The input is given from Standard Input in the following format:
$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

Output
Output the maximum possible total beauty of the illuminations on $1$ line.

Subtasks

1. ($10$ points) $N \le 16$, $M \le 16$
2. ($30$ points) $N \le 300$, $M \le 300$
3. ($30$ points) $N \le 4000$, $M \le 4000$
4. ($30$ points) No additional constraints.

Sample Input / Output

Sample Input 1

4 1
1 2 3 8
2 4

Sample Output 1

9

In this sample input, if he decorates trees $1$, $4$ with illuminations, the total beauty becomes $9$, which is the maximum. Since $L_1 = 2$, $R_1 = 4$, he cannot decorate $2$ or more trees among trees $2$, $3$, $4$ with illuminations. Note that, for example, he cannot decorate trees $1$, $2$, $4$ with illuminations.

Sample Input 2

5 2
2 3 9 5 6
1 3
2 4

Sample Output 2

15

Sample Input 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

Sample Output 3

4912419478