AT_joi2019_yo_e イルミネーション (Illumination)

JOI 氏在自家院子里种了 $ N $ 棵树，这些树排成一排，编号从 $ 1 $ 到 $ N $。 今年冬天，JOI 氏打算挑选一些树来挂彩灯，每挂彩灯的树有一个「美丽度」值，第 $ i $ 棵树的美丽度为 $ A_i $。 不过，JOI 氏意识到，如果在相邻的几棵树上都挂上彩灯，会显得过于刺眼。具体来说，对每组区间 $ j\ =\ 1,\ 2,\ \ldots,\ M $，从编号 $ L_j $ 到 $ R_j $ 的树中，最多只能在一棵树上挂彩灯。 现在，请你帮助计算在满足上述条件的前提下，能够获得的彩灯装饰美丽度的最大值。

输入通过标准输入提供，格式如下： > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ > $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \ldots $ $ L_M $ $ R_M $

输出一个整数，表示最大化的彩灯装饰美丽度。 ## 数据范围 - $ 1\ \leq\ N\ \leq\ 200000 $ - $ 1\ \leq\ M\ \leq\ 200000 $ - $ 1\ \leq\ A_i\ \leq\ 1000000000 $，其中 $ 1\ \leq\ i\ \leq\ N $ - $ 1\ \leq\ L_j\ \leq\ R_j\ \leq\ N $，其中 $ 1\ \leq\ j\ \leq\ M $ ### 子任务 1. (10 分) $ N\ \leq\ 16 $，$ M\ \leq\ 16 $ 2. (30 分) $ N\ \leq\ 300 $，$ M\ \leq\ 300 $ 3. (30 分) $ N\ \leq\ 4000 $，$ M\ \leq\ 4000 $ 4. (30 分) 没有额外限制 ### 示例说明 在此示例中，若在第 $ 1 $ 棵树和第 $ 4 $ 棵树上挂彩灯，能够获得的美丽度最大，总和为 $ 9 $。由于 $ L_1\ =\ 2 $ 和 $ R_1\ =\ 4 $，因此不能在第 $ 2 $、第 $ 3 $ 和第 $ 4 $ 棵树中超过一棵树上挂彩灯。再如，若在第 $ 1 $、第 $ 2 $ 和第 $ 4 $ 棵树上同时挂彩灯，也是违背限制条件的。 **本翻译由 AI 自动生成**

### 制約 - $ 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 $) ### 小課題 1. ($ 10 $ 点) $ N\ ≦\ 16 $，$ M\ ≦\ 16 $ 2. ($ 30 $ 点) $ N\ ≦\ 300 $，$ M\ ≦\ 300 $ 3. ($ 30 $ 点) $ N\ ≦\ 4000 $，$ M\ ≦\ 4000 $ 4. ($ 30 $ 点) 追加の制限はない． ### Sample Explanation 1 この入力例では，木 $ 1 $, $ 4 $ にイルミネーションを飾り付けると，美しさの合計が $ 9 $ となり最大となる．$ L_1\ =\ 2 $, $ R_1\ =\ 4 $ なので，木 $ 2 $, $ 3 $, $ 4 $ のうち $ 2 $ つ以上にイルミネーションを飾り付けることはできない．例えば木 $ 1 $, $ 2 $, $ 4 $ にイルミネーションを飾り付けることはできないことに注意せよ．