M国要在A城市与B城市之间建设5G基站，已知A城市与B城市的距离为$n$千米，工程师们已经考察在从A城市往B城市方向上1，2，...，n千米处建设5G基站的成本，分别是$w_1$，$w_2$，...，$w_n$。
为了保证通信质量，5G基站的选址还需要满足$m$条需求，其中第$i$条需求可以用$l_i$和$r_i$表示($1≤l_i≤r_i≤n$)，代表从A城市往B城市方向上$l_i$千米到$r_i$千米的位置之间（含两端）至少需要建设1座5G基站。
作为总工程师，您需要决定5G基站的数量与位置，并计算满足所有需求的最小总成本。
第一行输入两个整数$n$和$m$分别表示距离和需求数量。
接下来一行输入$n$个整数$w_1$，$w_2$，...，$w_n$分别表示从A城市往B城市方向上1，2，...，$n$千米处建设5G基站的成本。
接下来$m$行，第i行输入两个整数$l_i$和$r_i$($1≤l_i≤r_i≤n$)表示从A城市往B城市方向上$l_i$千米到$r_i$千米的位置之间（含两端）至少需要建设1座5G基站。
输出一行一个整数，表示满足所有需求的最小总成本。
输入
Input1： 5 3 3 2 4 1 100 1 3 2 4 5 5 Input2： 5 3 7 3 4 2 2 1 4 2 3 4 5
输出
Output1： 102 Output2： 5
数据范围：
$1≤n≤10^6$，$1≤m≤10^6$，$1≤w_i≤10^9$，$1≤l_i≤r_i≤n$
样例解释：
对于样例一，最优方案是在2千米和5千米处建设5G基站，总成本为102。
对于样例二，最优方案是在2千米和4千米处建设5G基站，总成本为5。
