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 自动生成