森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过$C_i$公斤。

公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从$S_j$号城市运输到$T_j$号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。

为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。

输入格式：
输入在第一行给出两个正整数N和Q$（2\le N\le 10^5,1\le Q\le 10^5）$，表示总共的城市数以及订单数量。

第二行给出(N−1)个数，顺次表示相邻两城市间的道路允许的最大运货重量$C_i$（i=0,⋯,N−2）。题目保证每个$C_i$是不超过$2^{31}$的非负整数。

接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。

输出格式：
在一行中输出可运输货物的最大重量。

输入样例：

10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2

输出样例：

7

应当选择交叉尽可能少的区间，减少路线冲突，这样才能使总运输质量最大，将所有询问按照右边界从小到大排（注意题目中给出的两个数 a、b，a 可能大于 b），用线段树维护区间的最小值，对每个查询区间找最小值加到答案中，并将区间整体减去这个最小值。
按右边界从小到大排利用了贪心的思想，右边界约靠左，其所能占的最大空间就越小，就能在更大空间中选择更多其他区间。
线段树中注意每次查询与修改将父节点的懒标记下传，修改完子节点后记得更新父节点的最小值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
struct node{
    int l,r;
    ll mn,lazy;
}tr[100010*4];
int n,q,arr[100010];
vector<pii> Q;
bool cmp(pii a,pii b)
{
    return a.y!=b.y?a.y<b.y:a.x<b.x;
}
void pushup(int u)
{
    tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
}
void pushdown(int u)
{
    tr[u<<1].lazy+=tr[u].lazy,tr[u<<1|1].lazy+=tr[u].lazy;
    tr[u<<1].mn+=tr[u].lazy,tr[u<<1|1].mn+=tr[u].lazy;
    tr[u].lazy=0;
}
void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    if(l==r) {
        tr[u].mn=arr[l];
    } else {
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
    int mid=tr[u].l+tr[u].r>>1;
    ll res=1e18;
    pushdown(u);
    if(l<=mid) res=query(u<<1,l,r);
    if(r>mid) res=min(res,query(u<<1|1,l,r));
    return res;
}
void modify(int u,ll add,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) {
        tr[u].mn+=add;
        tr[u].lazy+=add;
    } else {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,add,l,r);
        if(r>mid) modify(u<<1|1,add,l,r);
        pushup(u);
    }
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++) cin>>arr[i];
    while(q--) {
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b);
        Q.push_back({a,b});
    }
    sort(Q.begin(),Q.end(),cmp);
    build(1,1,n-1);
    ll ans=0;
    for(auto [a,b]:Q) {
        ll res=query(1,a+1,b);
        if(res>0) {
            ans+=res;
            modify(1,-res,a+1,b);
        }
    }
    cout<<ans<<'\n';
    return 0;
}