记录编号	90703	评测结果	AAAATTTTTTT
题目名称	最优挤奶法	最终得分	36
用户昵称	雪狼	是否通过	未通过
代码语言	C++	运行时间	7.003 s
提交时间	2014-03-08 20:22:31	内存使用	3.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 200000+10
#define REP(i,a,b) for(int i=a;i!=b+1;++i)
#define CLR(c,x) memset(c,x,sizeof(c))
#define INF ~0U>>2
#define eps 1e-9

using namespace std;
typedef unsigned long long LL; 


void setIO(string s){
	string in=s+".in",out=s+".out";
	freopen(in.c_str(),"r",stdin);
	freopen(out.c_str(),"w",stdout);
}

int n,d;
int m[maxn];
LL DP[maxn][2];

void work(int now){
	DP[0][0]=DP[0][1]=0;
	REP(i,now,n){
		DP[i][0]=max(DP[i-1][1],DP[i-1][0]);
		DP[i][1]=DP[i-1][0]+m[i];
	}
}

int main(){
    setIO("optmilk");
    
	LL ans=0;
	scanf("%d%d",&n,&d);
	REP(i,1,n)scanf("%d",m+i);
	work(1);
	
	int a;LL b;
	while(d--){
		scanf("%d%d",&a,&b);
		m[a]=b;
		work(a);
		ans+=max(DP[n][0],DP[n][1]);
		//cout<<ans<<' '<<d<<endl;
	}
	
	cout<<ans<<endl;
	
	return 0;
}