#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
const int V=1e5;
int n,m;
ll a[MAXN],b[MAXN],s;
template<const int M>
struct segt{
ll sum[MAXN<<2],s[MAXN<<2][M];int cnt[MAXN<<2];
void pushup(int id){
	cnt[id]=cnt[id<<1]+cnt[id<<1|1];
	for(int i=0;i<M;i++) s[id][i]=s[id<<1|1][i]+s[id<<1][((i-cnt[id<<1|1])%M+M)%M];
}
void add(int x,int d,int id=1,int l=0,int r=V){
	if(l==r){
		cnt[id]+=d;
		for(int i=0;i<M;i++) s[id][i]=1ll*l*(cnt[id]/M+(cnt[id]%M>i));
		return; 
	}
	int mid=l+r>>1;
	if(x<=mid) add(x,d,id<<1,l,mid);
	else add(x,d,id<<1|1,mid+1,r);
	pushup(id);
}
int count(){return cnt[1];}
int operator [](int x){return s[1][x];} 
};
segt<4> T1;// 正 
segt<2> T2;// 负 
void add(int a,int b,int x){
	s+=(a+b)*x;
	if(a<b) T1.add(b-a,x);
	else T2.add(V+b-a,x);
}
ll solve(){
	ll R=T1.count()&1?V:0,A=T1[0]-T1[1]-T1[2]+T1[3],B=(T1.count()&1?T2[1]-T2[0]+R:T2[0]-T2[1]-R);
	return (s-A-B)/2; 	
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		add(a[i],b[i],1);
	}
	cout<<solve()<<endl;
	for(int i=1;i<=m;i++){
		int p,x,y;cin>>p>>x>>y;
		add(a[p],b[p],-1);
		add(a[p]=x,b[p]=y,1);
		cout<<solve()<<endl;
	}
}