格罗宁根博物馆（Groninger Museum）的每一天都是不同的。有些日子美好、和平且安静，你可以花上一整天欣赏美丽的画作、雕塑和其他艺术品。而有些日子则更加繁忙，周末或公共假期会让博物馆挤满匆忙的游客、上涨的票价和尖叫的孩子。这种不适感变化很大：有些繁忙的日子因为有额外的学生折扣（studentenkorting）而变得更好，而有些安静的日子则因为地震风险而变得更糟。

从运河看到的格罗宁根博物馆。CC BY-SA 4.0，作者 Rob Koster，源自维基共享资源

博物馆还定期举办特殊的限时展览，例如关于当地足球俱乐部 FC Groningen、马提尼塔（Martinitoren）或 eierbal（一种当地美食）的展览。这些展览可能非常不规律：有些持续数周，有些仅持续一天，并且同一天可能会有多个展览。

作为一个骄傲的格罗宁根人，你希望将每个展览至少参观一次。幸运的是，你订阅了订阅邮件，因此提前知道了所有展览的开始和结束日期。此外，由于你是博物馆的常客，你已经观察到了所有的人流和地震规律，因此你确切地知道在任何特定日子参观博物馆会带来多少不适感。

你应该在哪些日子参观博物馆，以便在看完美术馆在可预见的未来计划的所有展览的同时，使你的总不适感降到最低？例如，考虑第一个样例。为了使总不适感最小，你应该在第二天参观前两个展览，并在第四天或第五天参观最后一个展览。

输入格式

输入包含以下内容：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示可预见的未来的天数以及在这些天内计划的展览数量。
• 第二行包含 $n$ 个整数 $c$（$1 \le c \le 10^9$），描述每天参观博物馆时你将承受的不适感。
• 接下来的 $m$ 行，每行包含两个整数 $s$ 和 $e$（$1 \le s \le e \le n$），描述一个展览的开始和结束日期。开始和结束日期是包含在内的：该展览可以在第 $s$ 天、第 $e$ 天以及它们之间的任何一天参观。

输出格式

输出参观格罗宁根博物馆所有展览时你将承受的最小总不适感。

样例

输入样例 1

5 3
1 1 3 1 1
1 3
2 3
3 5

输出样例 1

2

输入样例 2

6 3
1 2 4 4 2 1
1 4
2 5
3 6

输出样例 2

3

输入样例 3

11 2
3 1 4 1 5 9 2 6 5 3 5
5 10
1 1

输出样例 3

5