← 返回题目列表

AtCoder · joi2019_yo_e

E. 照明

中文机器翻译题面 查看原题

配点: 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 行。

小課題

  1. (10 点) N ≦ 16,M ≦ 16
  2. (30 点) N ≦ 300,M ≦ 300
  3. (30 点) N ≦ 4000,M ≦ 4000
  4. (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