配点: 100 点
問題文
JOI先生有 N 我拥有一棵树。这些树按顺序排列成一排 它们的编号最大为 1 从 N 的整数。
今年冬天,JOI先生决定选择一些树木,并用彩灯装饰它们。照明用美容 称为的值是固定的。树 用彩灯装饰 i 的美丽在于 A_i 。
JOI先生太近了 2 我注意到,如果我用照明装饰树的两侧,它可能会太亮。具体来说, 对于j = 1, 2, ..., M ,树 L_j, L_j + 1, ..., R_j 出 2 事实证明,您不应该用超过一种照明进行装饰。
根据这些条件找出装饰照明时总美感的最大值。
制約
- 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)
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 ... A_N L_1 R_1 L_2 R_2 ⋮ L_M R_M
出力
光照总美感最大值 1 行。
小課題
- (10 点) N ≦ 16,M ≦ 16
- (30 点) N ≦ 300,M ≦ 300
- (30 点) N ≦ 4000,M ≦ 4000
- (30 点)没有额外的限制。
入力例 1
4 1 1 2 3 8 2 4
出力例 1
9
在此输入示例中,树 当你用彩灯装饰 1, 4 时,整体美感会增加。 9 ,这是最大值。L_1 = 2, R_1 = 4 因此,树 2, 3, 4 出 2 无法使用多于一种的照明进行装饰。例如,木头 请注意, 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