#include<cstdio>
#include<cstdlib>
#define LL long long
#define zxc 200000
using namespace std;
LL n,m,d[zxc],l[zxc],r[zxc],left[zxc],right[zxc],sumleft[zxc],sumright[zxc],all[zxc],pos[zxc],f[zxc],ans,r1,r2;

LL max(LL x,LL y)
{ return x<y?y:x;}

void pushup(LL x)
{
	d[x]=max(d[left[x]]+sumright[right[x]],d[right[x]]+sumleft[left[x]]);
	sumright[x]=max(sumright[left[x]]+sumright[right[x]],all[left[x]]+d[right[x]]);
	sumleft[x]=max(sumleft[left[x]]+sumleft[right[x]],d[left[x]]+all[right[x]]);
	all[x]=max(sumright[left[x]]+all[right[x]],sumleft[right[x]]+all[left[x]]);
}

void change(LL x,LL y)
{
	d[x]=y;
	for(x=f[x];x;x=f[x]) pushup(x);
}

int main()
{
	freopen("optmilk.in","r",stdin);
	freopen("optmilk.out","w",stdout);
	LL i,ll=0,rr=1,mid;
	scanf("%lld%lld",&n,&m);
	l[1]=1; r[1]=n;
	while(ll!=rr)
	{
		ll++; if(l[ll]==r[ll]) pos[l[ll]]=ll; else
		{
			mid=(l[ll]+r[ll])/2;
			l[++rr]=l[ll]; r[rr]=mid; left[ll]=rr; f[rr]=ll;
			l[++rr]=mid+1; r[rr]=r[ll]; right[ll]=rr; f[rr]=ll;
		}
	}
	for(i=1;i<=n;i++) {scanf("%lld",&r1); change(pos[i],r1);}
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld",&r1,&r2);
		change(pos[r1],r2);
		ans+=d[1];
	}
	printf("%lld",ans);
	return 0;
}