Updates

[2026-8-5] 本题于 2026 年 8 月 5 日更新数据范围，以往使用暴力方法的正确提交无法通过，请重写^[1]。

题目描述

打靶摊上一共有 $n$ 个靶子排成一排，编号为 $1$ ~ $n$。李华付了 $q$ 元钱，也就代表他可以玩 $q$ 次这个游戏。

每次游戏时，李华会选择两个端点 $l_i$ 和 $r_i$，并同时射向 $[l_i,r_i]$ 这些靶子，并且作为神箭手的他 $100\%$ 会射中。每个靶子对应的奖励都可能不一样，所以李华射中这些靶子拿到的奖励也可能不一样（奖励可以重复领取）。

另外，李华可以在打靶前调整每个靶子对应的奖励，从而让他获得的奖励最大化（数字越大代表奖励越多）。请你帮帮他。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示靶子的数量和李华付的钱数。
第二行包含 $n$ 个整数 $a_i$，表示每个靶子对应的奖励。
接下来 $q$ 行，每行两个整数 $l_i$ 和 $r_i$，表示李华决定射击的左端点和右端点。

输出格式

输出一个整数，表示李华最后能拿到的奖励总和。

输入输出样例

4 3
1 3 2 4
1 2
2 3
1 4

23

说明/提示

样例解释

在样例中，李华可以设置奖励顺序为 3 4 2 1，从而获得最大的奖励数量。

数据范围

对于 $30\%$ 的数据，$1 \le n,q \le 10^3$。
对于 $100\%$ 的数据，$1 \le n,q \le 10^5,1 \le l_i \le r_i \le n,1 \le a_i \le 10^3$。