#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define sz(x) int(x.size())

using ll = int64_t;
using vi = vector<int>;
using pii = pair<int, int>;

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

void wassert(bool b) {
	if (!b) {
		cout << "NMSL" << endl;
		exit(0);
	}
}

mt19937 mt(19260817);
template <int M>
struct treap_node {
	array<treap_node*, 2> c{nullptr, nullptr};
	mt19937::result_type pri = mt();
	int sz = 1;
	pair<int, int> val;
	array<ll, M> sum;

	void update() {
		sz = 1;
		if (c[0]) {
			assert(c[0]->val < val);
			sz += c[0]->sz;
			sum = c[0]->sum;
			sum[c[0]->sz % M] += val.first;
		} else {
			sum.fill(0);
			sum[0] = val.first;
		}
		if (c[1]) {
			assert(val < c[1]->val);
			for (int r = 0; r < M; r++) {
				sum[(sz + r) % M] += c[1]->sum[r];
			}
			sz += c[1]->sz;
		}
	}
};

template <class node>
node* merge(node* a, node* b) {
	if (!a) return b;
	if (!b) return a;
	node* r;
	if (a->pri < b->pri) {
		r = a;
		r->c[1] = merge(a->c[1], b);
	} else {
		r = b;
		r->c[0] = merge(a, b->c[0]);
	}
	r->update();
	return r;
}

template <class node>
pair<node*, node*> split_by_sz(node* a, int lsz) {
	if (!a) {
		assert(lsz == 0);
		return {nullptr, nullptr};
	}
	assert(0 <= lsz && lsz <= a->sz);
	if (lsz == 0) return {nullptr, a};
	if (lsz == a->sz) return {a, nullptr};
	int c0sz = (a->c[0] ? a->c[0]->sz : 0);
	node *x, *y;
	if (lsz <= c0sz) {
		y = a;
		tie(x, y->c[0]) = split_by_sz(a->c[0], lsz);
	} else {
		x = a;
		tie(x->c[1], y) = split_by_sz(a->c[1], lsz - c0sz - 1);
	}
	a->update();
	return {x, y};
}

template <class node>
pair<node*, node*> split_by_val(node* a, const pair<int, int>& v) {
	if (!a) {
		return {nullptr, nullptr};
	}
	node *x, *y;
	if (a->val >= v) {
		y = a;
		tie(x, y->c[0]) = split_by_val(a->c[0], v);
	} else {
		x = a;
		tie(x->c[1], y) = split_by_val(a->c[1], v);
	}
	a->update();
	return {x, y};
}

template <class node>
node* insert_node(node* n, node* a) {
	auto [x, y] = split_by_val(a, n->val);
	return merge(x, merge(n, y));
}

template <class node>
node* remove_node(node* n, node* a) {
	auto [x, y] = split_by_val(a, n->val);
	auto [z, w] = split_by_sz(y, 1);
	assert(z == n);
	return merge(x, w);
}

template <class node>
void travel(node* a) {
	if (!a) return;
	travel(a->c[0]);
	cerr << a->val.first << endl;
	travel(a->c[1]);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, Q;
	cin >> N >> Q;

	vector<treap_node<4>> nodes_small(N);
	vector<treap_node<2>> nodes_large(N);
	for (int i = 0; i < N; i++) {
		nodes_small[i].val = {0, i};
		nodes_small[i].update();
		nodes_large[i].val = {0, i};
		nodes_large[i].update();
	}
	treap_node<4>* sroot = nullptr;
	treap_node<2>* lroot = nullptr;
	ll bsum = 0;
	vector<int> A(N), B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		bsum += B[i];
		int x = A[i] - B[i];
		if (x <= 0) {
			nodes_small[i].val.first = x;
			sroot = insert_node(&nodes_small[i], sroot);
		} else {
			nodes_large[i].val.first = x;
			lroot = insert_node(&nodes_large[i], lroot);
		}
	}

	auto query = [&]() -> ll {
		//travel(sroot);
		int srootsz = 0;
		ll extra = 0;
		if (sroot) {
			extra += sroot->sum[0] + sroot->sum[3];
			srootsz = sroot->sz;
		}
		if (lroot) {
			extra += lroot->sum[srootsz % 2];
		}
		return bsum + extra;
	};
	auto query_naive = [&]() -> ll {
		ll res = bsum;
		vector<int> smalls, larges;
		for (int i = 0; i < N; i++) {
			int x = A[i] - B[i];
			if (x <= 0) {
				smalls.push_back(x);
			} else {
				larges.push_back(x);
			}
		}
		sort(smalls.begin(), smalls.end());
		for (int i = 0; i < int(smalls.size()); i++) {
			int r = i % 4;
			if (r == 0 || r == 3) {
				res += smalls[i];
			}
		}
		sort(larges.begin(), larges.end());
		for (int i = int(smalls.size()) % 2; i < int(larges.size()); i += 2) {
			res += larges[i];
		}
		return res;
	};

	//cout << query() << '\n';
	cout << query_naive() << '\n';

	for (int q = 0; q < Q; q++) {
		int i, a, b;
		cin >> i >> a >> b;
		i--;
		{
			int x = A[i] - B[i];
			if (x <= 0) {
				sroot = remove_node(&nodes_small[i], sroot);
			} else {
				lroot = remove_node(&nodes_large[i], lroot);
			}
		}
		bsum -= B[i];
		A[i] = a, B[i] = b;
		bsum += B[i];
		{
			int x = A[i] - B[i];
			if (x <= 0) {
				nodes_small[i].val.first = x;
				sroot = insert_node(&nodes_small[i], sroot);
			} else {
				nodes_large[i].val.first = x;
				lroot = insert_node(&nodes_large[i], lroot);
			}		
		}
		cout << query() << '\n';
	}
}