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。