คำอธิบายโจทย์

คุณ JOI มีต้นไม้ $N$ ต้นอยู่ในบริเวณบ้านของตน ต้นไม้เหล่านี้เรียงกันเป็นแถวเดียวและมีหมายเลขกำกับตามลำดับด้วยจำนวนเต็มตั้งแต่ $1$ ถึง $N$

ในฤดูหนาวนี้ คุณ JOI ตัดสินใจเลือกต้นไม้บางต้นเพื่อติดไฟประดับ ไฟประดับจะมีค่าที่เรียกว่า ความสวยงาม กำหนดไว้ ความสวยงามเมื่อติดไฟประดับที่ต้นไม้ $i$ คือ $A_i$

คุณ JOI สังเกตเห็นว่าหากติดไฟประดับลงบนต้นไม้ทั้ง $2$ ต้นที่อยู่ใกล้กันเกินไป อาจทำให้แสบตาเกินไปได้ กล่าวคือ สำหรับ $j = 1, 2, \dots, M$ พบว่าไม่ควรติดไฟประดับให้กับต้นไม้ตั้งแต่ $2$ ต้นขึ้นไปจากบรรดาต้นไม้ $L_j$, $L_j + 1$, $\dots$, $R_j$

จงหาค่ามากที่สุดของผลรวมความสวยงามเมื่อติดไฟประดับตามเงื่อนไขนี้

ข้อจำกัด

• $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$ บรรทัด

งานย่อย (Subtasks)

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$ ต้นขึ้นไปจากต้นไม้ $2$, $3$, $4$ ได้ โปรดสังเกตว่าไม่สามารถติดไฟประดับที่ต้นไม้ $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