//USACO 2013 December Contest, Gold Problem 2. Optimal Milking


#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define m_p make_pair
#define l_b lower_bound
#define u_b upper_bound
#define ll long long int
#define eps 1e-9
#define inf 1e9
using namespace std;
int a[50100];
struct data
{
    ll ylyr,ylnr,nlnr,nlyr;
    void init(int val)
    {
        ylyr=ylnr=nlnr=nlyr=0;
        ylyr=val;
    }
    ll getmax()
    {
        return max(ylyr,max(ylnr,max(nlyr,nlnr)));
    }
}dnull;

struct SegementTree
{
    static const int maxN = 50100;
    int n;
    data tree[maxN*4];

    SegementTree(){};
    void setN(int _n)
    {
        this->n=_n;
    }
    inline data merge(data lft_v,data rgt_v)//these two are values, NOT indexes
    {
        data res;
        res.init(0);
        res.ylyr=max( max(lft_v.ylyr+rgt_v.nlyr,lft_v.ylnr+rgt_v.ylyr) , lft_v.ylnr+rgt_v.nlyr);
        res.ylnr=max(max(lft_v.ylyr + rgt_v.nlnr ,lft_v.ylnr+rgt_v.ylnr),lft_v.ylnr+rgt_v.nlnr);
        res.nlnr=max(max(lft_v.nlyr + rgt_v.nlnr ,lft_v.nlnr+rgt_v.ylnr),lft_v.nlnr+rgt_v.nlnr);
        res.nlyr=max(max(lft_v.nlyr + rgt_v.nlyr ,lft_v.nlnr+rgt_v.ylyr),lft_v.nlnr+rgt_v.nlyr);
        return res;
    }
    void update(int cn,int st,int ed,int l,int r,int v)
    {
        if(l>ed || r<st) return;
        if(st>=l && ed<=r)
        {
            tree[cn].init(v);
            return;
        }
        int mid=(st+ed)>>1,lft=cn*2,rgt=lft+1;
        update(lft,st,mid,l,r,v);
        update(rgt,mid+1,ed,l,r,v);
        tree[cn]=merge(tree[lft],tree[rgt]);
    }

    void update(int v,int l,int r=-1)//updatedValue , indexes
    {
         if(r==-1) r=l;
         update(1,1,n,l,r,v);
    }
}S;


int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    S.setN(n);
    for(int i=1;i<=n;i++) S.update(a[i],i);
    ll ans=0;
    for(int i=1;i<=q;i++)
    {
        int p,amount;
        cin>>p>>amount;
        S.update(amount,p);
        ans+=S.tree[1].getmax();
    }
    cout<<ans<<endl;
}