### 问题描述 ACM/ICPC 比赛的赛制非常有意思，它的罚时计算系统是整个比赛最意思的地方。 具体的计算方案如下： 我们假设有 $n$ 个题，你提交并且通过的时间是第 $s_i$ 分钟，我们认为你本题的罚时是 $s_i$，那么对于所有的题目，你的总罚时就是 $\sum _{i=1} ^n s_i$。当然，如果你没有通过某个题目，那么罚时会计算在内。 小蓝现在在参加一个比赛，他面对 $n$ 个题，其中第 $i$ 个题他需要 $p_i$ 分钟才能解决，当他解决之后，他可以立即提交，你可以理解为提交消耗时间，由于他非常聪明，所以他只要提交就能通过，但是同一时刻他只能同时解决一道题。 现在由于提交系统出了一些问题，小蓝只能在一些时间段才能提交，这些时间段用一些闭区间 $[l_i, r_i]$ 来表示，表示在 $[l_i, r_i]$ 时间段类可以提交。 他可以任意规划解决问题的顺序，他想问你最后的总罚时最小是多少？ ### 输入格式 第一行输入两个整数 $n, m$，代表题目数量和可以提交的时间段。 第二行输入 $n$ 个整数 $p_1,p_2,p_3,...,p_n$，代表每道题需要的时间，时间单位为分钟。 接下来 $m$ 行，每行两个整数 $[l_i, r_i]$，表示可以在时间区间 $[l_i, r_i]$ 可以提交。 ### 输出格式 输出一个整数，代表最小的总罚时，时间单位为分钟。 ### 样例输入 ``` 3 2 7 3 2 5 6 10 20 ``` ### 样例输出 ``` 22 ``` ### 说明 第 $2$ 分钟解决题目 $3$，第 $5$ 分钟解决题目 $2$，第 $5$ 分钟提交 $2,3$ 题，第 $12$ 分钟解决题目 $1$，并且提交，总罚时为 $22$ 分钟。 ### 评测数据范围 $1 \le n,m \le 10^4, 1 \le p_i \le 10^5, 1 \le l_i \le r_i \le 10^9$。 保证当 $i \gt 1$ 时，满足 $l_i \gt r_{i-1}$，并且 $r_n \ge \sum_{i=1} ^n p_i$。