题目背景

元旦到了，李华跑到街上逛庙会。他在一个摊位前面看到了这样的提示：“打靶游戏，射中对应的靶子可以获得奖励。$1$ 元 $1$ 次，先到先得！”李华高兴极了，赶紧凑了过去。

题目描述

打靶摊上一共有 $n$ 个靶子排成一排，编号为 $1,2,...,n$。李华付了 $q$ 元钱，也就代表他可以玩 $q$ 次这个游戏。每次游戏时，李华会选择两个端点 $l_i$ 和 $r_i$，并同时射向 $l_i,l_i+1,...,r_i$ 这些靶子，并且作为神箭手的他 $100\%$ 会射中。每个靶子对应的奖励都可能不一样，所以李华射中这些靶子拿到的奖励也可能不一样（奖励可以重复领取）。另外，李华充值了打靶摊的 VIP 会员，这代表他可以在打靶前调整每个靶子对应的奖励，从而让他获得的奖励最大化（数字越大代表奖励越多）。请你帮帮他。

输入格式

第一行包含两个整数 $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，从而获得最大的奖励数量。

数据范围与规模：

• $1≤n≤10^3$
• $1≤q≤10^3$
• $1≤a_i≤2×10^5$
• $1≤l_i≤r_i≤n$