You may permute the array once before answering all inclusive one-based range queries. Maximize the sum of all query results.

Input

The first line contains \(N\) and \(Q\). The second line contains \(N\) integers. Each of the next \(Q\) lines contains \(L\) and \(R\).

The input satisfies:

• \(1 \le N, Q \le 2 * 10^5\)
• \(1 \le A_i \le 2 * 10^5\)
• \(1 \le L \le R \le N\)

Output

Print the maximum possible total over all queries.

Example

Input

105 134
26573 191487 71428 71184 68069 149070 23902 153772 152068 195847 93965 165349 75432 23290 176569 107798 42830 132393 182491 73271 42058 102318 78523 53899 92612 34639 193167 94170 156264 196995 128374 46418 134463 192588 75092 57902 99568 116214 52368 166324 41940 135487 102582 67502 84719 50860 77727 69493 44391 76774 147967 186502 136467 141229 182369 138180 161828 64180 159923 25118 86627 75780 163649 19393 100407 103465 134437 4314 191763 39178 191240 165207 141607 157270 101578 106586 134603 68737 189641 124053 138535 25281 25052 89995 57834 50800 197182 161911 148588 188535 188369 41252 90975 1429 110639 27076 108947 179622 111309 197340 18014 146470 48241 39693 18458
31 34
35 53
14 52
3 76
1 75
20 61
13 98
1 11
69 83
66 104
83 93
35 52
72 87
30 79
4 48
59 96
24 84
71 97
12 75
83 99
8 41
7 24
43 102
4 77
75 80
46 46
68 68
29 81
79 83
53 56
46 96
56 69
1 105
7 63
9 43
93 96
98 101
7 84
32 53
34 43
90 92
19 92
38 80
61 98
80 81
105 105
67 84
98 98
79 93
97 104
11 28
12 68
73 94
10 49
93 101
21 74
63 105
62 69
52 54
7 55
70 84
19 21
84 90
3 75
50 58
17 36
12 94
66 70
97 105
38 57
31 56
65 94
71 104
84 99
78 82
49 56
42 94
46 75
54 67
75 98
45 86
95 101
64 71
58 64
28 69
50 101
95 97
42 61
2 52
98 102
7 13
13 83
9 30
43 71
64 77
21 25
75 87
21 24
50 70
94 101
75 99
11 59
3 90
75 78
98 98
34 53
84 97
36 57
62 79
93 102
90 95
73 83
88 93
48 77
52 79
87 99
41 71
52 87
8 22
103 105
89 98
99 104
32 82
4 58
41 94
60 102
33 40
103 103
49 51
104 105
84 93
89 90
59 76
28 60

Output

443100776