//from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int f[1 << 10][1 << 10][2][2];

int dp(int mask1, int mask2, bool p, bool l) {
  if (mask1 == (1 << n) - 1 && mask1 == mask2) return 0;
  auto &ret = f[mask1][mask2][p][l];
  if (ret > -1) return ret;

  if (p) {
    ret = 1e9;
    for (int i = 1; i <= n; ++i) {
      if (mask1 >> i - 1 & 1) continue;
      int c = (mask2 >> i - 1 & 1) ? b[i] : a[i];
      int nmask = (mask1 | (1 << i - 1));
      ret = min(ret, dp(nmask, mask2, l == 1 ? 1 - p : p, (l + 1) % 2) + c);

    }
  } else {
    ret = 0;
    for (int i = 1; i <= n; ++i) {
      if (mask2 >> i - 1 & 1) continue;
      int nmask = (mask2 | (1 << i - 1));
      ret = max(ret, dp(mask1, nmask, l == 1 ? 1 - p : p, (l + 1) % 2));
    }
  }
  return ret;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
  memset(f, -1, sizeof f);
  cout << dp(0, 0, 1, 1) << "\n";
  for (int i = 1; i <= m; ++i) {
    int t, x, y; cin >> t >> x >> y; a[t] = x; b[t] = y;
    memset(f, -1, sizeof f);
    cout << dp(0, 0, 1, 1) << "\n";
  }

}