Illumination

Time limit2sMemory limit512 MB

Summary

Choose a subset of trees to decorate, maximizing total beauty, so that for each of M given intervals at most one tree inside it is chosen.

Level: Hard8 of 10
Topics: Dynamic programming, Segment tree, Greedy, Sorting
Solved: No attempts yet

Problem

JOI has N trees on his property. The trees are lined up in a row and numbered 1 through N in order.

This winter, JOI decided to choose some of the trees and decorate them with illuminations. An illumination has a value called beauty. The beauty of decorating tree i with an illumination is A_i.

JOI realized that decorating two trees that are too close together with illuminations can be too dazzling. Specifically, for j = 1, 2, ..., M, it turned out that no more than one of the trees L_j, L_j + 1, ..., R_j may be decorated with an illumination.

Find the maximum total beauty when decorating illuminations under this condition.

Input

The input is given from 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

Print the maximum total beauty of the illuminations on one line.

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)

Examples3

Example 1
Input
```
4 1
1 2 3 8
2 4
```
Expected output
```
9
```
Example 2
Input
```
5 2
2 3 9 5 6
1 3
2 4
```
Expected output
```
15
```

Example 3

Input

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

Expected output

4912419478