Alpha Country has a wind farm that is planned on a square grid of N rows and N columns. The rows are numbered from 1 to N from top to bottom, and the columns are numbered from 1 to N from left to right. The farm has M wind turbines numbered from 1 to M. The i-th turbine (1 ≤ i ≤ M) is located at the cell in row Ri and column Ci with a power output of Wi watts. The farm owner has just signed a contract to supply electricity to a partner. The farm will have to install three power lines, each passing through one row or one column of the grid. The lines can intersect but cannot overlap. The total power supplied to the partner is the sum of the power of the turbines located on at least one of the three lines. The farm needs to find a way to install three power lines so that the total power supplied is as large as possible.

In addition, the company has Q adjustment plans. The j-th adjustment plan (1 ≤ j ≤ Q) is to increase the power of the Tj-th turbine by Dj watts and keep the power Wi of all other turbines i different from Tj the same as the original initial state. Note that the plans are independent, meaning that each plan is only applied to the initial state of the farm.

Requirement: Determine the maximum possible total power when installing three power lines with the initial state of the farm and in each adjustment plan.

Input From the text file THREE.INP:

The first line contains a positive integer T indicating the number of test cases. Each group of lines in the T following groups describes a test case with the following structure: The first line contains three integers N, M, and Q representing the size of the grid, the number of turbines, and the number of adjustment plans (3 ≤ N ≤ 10^9; 3 ≤ M ≤ 10^5; 1 ≤ Q ≤ 10^5).

The i-th of the next M lines contains three integers Ri, Ci, and Wi representing the row, column, and power of the i-th turbine. The data ensures that no two turbines are placed in the same cell (1 ≤ Ri, Ci ≤ N; 1 ≤ Wi ≤ 10^9).

The i-th of the next Q lines contains two integers Tj and Dj representing the adjustment plan to increase the power of the Tj-th turbine by Dj watts (1 ≤ Tj ≤ M; 1 ≤ Dj ≤ 10^18).

Let ∑M and ∑Q be the sums of all values of M and Q in all T test cases. The data ensures 1 ≤ ∑M, ∑Q ≤ 2 × 10^5. The numbers on the same line are separated by spaces. Output Write to the text file THREE.OUT:

T groups of lines, each line is the result of the corresponding test case with the following structure:

The first line shows a positive integer which is the maximum total power found with the initial state of the farm.

The j-th of the next Q lines shows the maximum total power found with the j-th adjustment plan.

#include <bits/stdc++.h>

using namespace std;

#define REP(i, b) for (int i = 0; i < (b); i++)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define all(a) a.begin(), a.end()
#define pb push_back
#define fi first
#define se second
#define el '\n'

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvll;

const ll MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  freopen("THREE.INP", "r", stdin);
  freopen("THREE.OUT", "w", stdout);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 4>> a(m);
    REP(id, m) {
      int i, j, v;
      cin >> i >> j >> v;
      a[id] = {i, j, v, id};
    }
    auto R = [&](array<int, 4> lhs, array<int, 4> rhs) {
      return lhs[0] < rhs[0];
    };
    auto C = [&](array<int, 4> lhs, array<int, 4> rhs) {
      return lhs[1] < rhs[1];
    };
    auto P = [&](array<int, 4> lhs, array<int, 4> rhs) {
      return lhs[3] < rhs[3];
    };
    auto Discrete = [&](int coeff) {
      int cnt = -1, prev = -1;
      REP(id, m) {
        cnt += (a[id][coeff] != prev);
        prev = a[id][coeff];
        a[id][coeff] = cnt;
      }
    };
    int op = 0;
    sort(all(a), R);
    Discrete(0);
    sort(all(a), C);
    Discrete(1);
    sort(all(a), P);
    vector<pair<int, ll>> query(q);
    REP(x, q) {
      int id;
      ll d;
      cin >> id >> d;
      id--;
      query[x] = {id, d};
    }
    vi list_row, list_col;
    vector<vector<pi>> row, col;
    vector<vector<pair<int, ll>>> row_query;
    vll sum_row, sum_col;
    multiset<pair<ll, int>, greater<pair<ll, int>>> sum_row_set, sum_col_set;
    vvi best_row;
    vector<pair<ll, int>> best_for_col, second_best_for_col;
    multiset<pair<ll, int>, greater<pair<ll, int>>> best_for_col_set;
    auto Init = [&]() {
      list_row.clear();
      list_col.clear();
      row.clear();
      col.clear();
      row_query.clear();
      sum_row.clear();
      sum_col.clear();
      sum_row_set.clear();
      sum_col_set.clear();
      best_row.clear();
      best_for_col.clear();
      second_best_for_col.clear();
      best_for_col_set.clear();
      REP(r, 2) {
        sum_row_set.insert({0, -1});
        sum_col_set.insert({0, -1});
        best_for_col_set.insert({{0, -1}});
      }
      row.resize(m);
      col.resize(m);
      vi seen_row(1e5 + 5, 0), seen_col(1e5 + 5, 0);
      REP(id, m) {
        int i = a[id][0], j = a[id][1], v = a[id][2];
        row[i].pb({j, v});
        col[j].pb({i, v});
        if (seen_row[i] == 0) {
          list_row.pb(i);
          seen_row[i] = 1;
          ;
        }
        if (seen_col[j] == 0) {
          list_col.pb(j);
          seen_col[j] = 1;
        }
      }
      sum_row.resize(m);
      sum_col.resize(m);
      for (int& i : list_row) {
        for (auto& p : row[i]) {
          sum_row[i] += 1ll * p.se;
        }
        sum_row_set.insert({sum_row[i], i});
      }
      for (int& j : list_col) {
        for (auto& p : col[j]) {
          sum_col[j] += 1ll * p.se;
        }
        sum_col_set.insert({sum_col[j], j});
      }
      best_row.resize(m);
      best_for_col.resize(m);
      second_best_for_col.resize(m);
      for (int& j : list_col) {
        for (auto p : col[j]) {
          int i = p.fi, v = p.se;
          sum_row_set.erase({sum_row[i], i});
          sum_row_set.insert({sum_row[i] - 1ll * v, i});
        }
        auto it = sum_row_set.begin();
        best_for_col[j] = {(*it).fi + sum_col[j], (*it).se};
        best_for_col_set.insert({best_for_col[j].fi, j});
        best_row[(*it).se].pb(j);
        it++;
        second_best_for_col[j] = {(*it).fi + sum_col[j], (*it).se};
        for (auto p : col[j]) {
          int i = p.fi, v = p.se;
          sum_row_set.erase({sum_row[i] - 1ll * v, i});
          sum_row_set.insert({sum_row[i], i});
        }
      }
      row_query.resize(m);
      REP(x, q) {
        int id = query[x].fi;
        int i = a[id][0];
        ll d = query[x].se;
        row_query[i].pb({x, d});
      }
    };
    ll res = 0;
    vll ans(q, 0);
    auto TwoRows = [&](int i) {
      ll ret = sum_row[i];
      sum_row_set.erase({sum_row[i], i});
      auto it = sum_row_set.begin();
      ret += (*it).fi;
      it++;
      ret += (*it).fi;
      sum_row_set.insert({sum_row[i], i});
      return ret;
    };
    auto TwoCols = [&](int i) {
      ll ret = sum_row[i];
      for (auto& p : row[i]) {
        int j = p.fi, v = p.se;
        sum_col_set.erase({sum_col[j], j});
        sum_col_set.insert({sum_col[j] - 1ll * v, j});
      }
      auto it = sum_col_set.begin();
      ret += (*it).fi;
      it++;
      ret += (*it).fi;
      for (auto& p : row[i]) {
        int j = p.fi, v = p.se;
        sum_col_set.erase({sum_col[j] - 1ll * v, j});
        sum_col_set.insert({sum_col[j], j});
      }
      return ret;
    };
    auto OneRowOneCol = [&](int i) {
      ll ret = sum_row[i];
      for (int& j : best_row[i]) {
        best_for_col_set.erase({best_for_col[j].fi, j});
        best_for_col_set.insert({second_best_for_col[j].fi, j});
      }
      for (auto& p : row[i]) {
        int j = p.fi, v = p.se;
        if (best_for_col[j].se != i) {
          best_for_col_set.erase({best_for_col[j].fi, j});
          best_for_col_set.insert({best_for_col[j].fi - 1ll * v, j});
        } else {
          best_for_col_set.erase({second_best_for_col[j].fi, j});
          best_for_col_set.insert({second_best_for_col[j].fi - 1ll * v, j});
        }
      }
      auto it = best_for_col_set.begin();
      ret += (*it).fi;
      for (auto& p : row[i]) {
        int j = p.fi, v = p.se;
        if (best_for_col[j].se != i) {
          best_for_col_set.erase({best_for_col[j].fi - 1ll * v, j});
          best_for_col_set.insert({best_for_col[j].fi, j});
        } else {
          best_for_col_set.erase({second_best_for_col[j].fi - 1ll * v, j});
          best_for_col_set.insert({second_best_for_col[j].fi, j});
        }
      }
      for (int& j : best_row[i]) {
        best_for_col_set.erase({second_best_for_col[j].fi, j});
        best_for_col_set.insert({best_for_col[j].fi, j});
      }
      return ret;
    };
    auto Solve = [&]() {
      ll ret = 0;
      for (int& i : list_row) {
        ll best = max({OneRowOneCol(i), TwoCols(i), TwoRows(i)});
        for (auto& p : row_query[i]) {
          int x = p.fi;
          ll d = p.se;
          ans[x] = max(ans[x], best + d);
        }
        ret = max(ret, best);
      }
      return ret;
    };
    REP(r, 2) {
      Init();
      res = max(res, Solve());
      REP(id, m) { swap(a[id][0], a[id][1]); }
    }
    cout << res << el;
    REP(x, q) { cout << max(res, ans[x]) << el; }
  }
  return 0;
}