Problem Description

JOI has $ N $ trees on his property. These trees are arranged in a row and are numbered from $ 1 $ to $ N $.

This winter, JOI decided to decorate some of the trees with illuminations. Each illumination has a value called beauty. The beauty of the illumination on tree $ i $ is $ A_i $.

JOI noticed that decorating two trees that are too close to each other with illuminations might be too dazzling. Specifically, for $ j = 1, 2, ..., M $, it was found that no more than two of the trees $ L_j, L_j + 1, ..., R_j $ should be decorated with illuminations.

Find the maximum total beauty of the illuminations when decorating according to these conditions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ ⋮ $ $ L_M $ $ R_M $

Output Format

Output the maximum total beauty of the illuminations in one line.

Sample Input and Output

Sample Input #1

4 1
1 2 3 8
2 4

Sample Output #1

9

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

Notes/Hints

Constraints

• $ 1 ≦ N ≦ 200000 (= 2×10^5) $
• $ 1 ≦ M ≦ 200000 (= 2×10^5) $
• $ 1 ≦ A_i ≦ 1000000000 (= 10^9) $ ($ 1 ≦ i ≦ N $)
• $ 1 ≦ L_j ≦ R_j ≦ N $ ($ 1 ≦ j ≦ M $)

Subtasks

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

Sample Explanation 1

In this input example, decorating trees $ 1 $ and $ 4 $ with illuminations results in the maximum total beauty of $ 9 $. Since $ L_1 = 2 $ and $ R_1 = 4 $, no more than two of the trees $ 2, 3, 4 $ can be decorated with illuminations. Note that decorating trees $ 1, 2, 4 $ with illuminations is not possible.

见题面 Input 部分

见题面 Output 部分