Yet Another Maxflow Problem
Contest: Educational Codeforces Round 34 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, flows, graphs

In this problem you will have to deal with a very special network.

The network consists of two parts: part A and part B. Each part consists of n vertices; i-th vertex of part A is denoted as Ai, and i-th vertex of part B is denoted as Bi.

For each index i (1 ≤ i < n) there is a directed edge from vertex Ai to vertex Ai + 1, and from Bi to Bi + 1, respectively. Capacities of these edges are given in the input. Also there might be several directed edges going from part A to part B (but never from B to A).

You have to calculate the maximum flow value from A1 to Bn in this network. Capacities of edges connecting Ai to Ai + 1 might sometimes change, and you also have to maintain the maximum flow value after these changes. Apart from that, the network is fixed (there are no changes in part B, no changes of edges going from A to B, and no edge insertions or deletions).

Take a look at the example and the notes to understand the structure of the network better.

Input format:
The first line contains three integer numbers n, m and q (2 ≤ n, m ≤ 2·105, 0 ≤ q ≤ 2·105) — the number of vertices in each part, the number of edges going from A to B and the number of changes, respectively.

Then n - 1 lines follow, i-th line contains two integers xi and yi denoting that the edge from Ai to Ai + 1 has capacity xi and the edge from Bi to Bi + 1 has capacity yi (1 ≤ xi, yi ≤ 109).

Then m lines follow, describing the edges from A to B. Each line contains three integers x, y and z denoting an edge from Ax to By with capacity z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109). There might be multiple edges from Ax to By.

And then q lines follow, describing a sequence of changes to the network. i-th line contains two integers vi and wi, denoting that the capacity of the edge from Avi to Avi + 1 is set to wi (1 ≤ vi < n, 1 ≤ wi ≤ 109).

Output format:
Firstly, print the maximum flow value in the original network. Then print q integers, i-th of them must be equal to the maximum flow value after i-th change.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
This is the original network in the example:

Example input:
4 3 2
1 2
3 4
5 6
2 2 7
1 4 8
4 3 9
1 100
2 100

Example output:
9
14
14

Editorial:
First of all, let's calculate minimum cut instead of maximum flow.
The value of the cut is minimum if we choose S (the first set of the cut) as x first vertices of part A and y first vertices of part B (1 ≤ x ≤ n, 0 ≤ y < n). That's because if i is the minimum index such that $$A_i \notin S$$, then we don't have to add any vertices Aj such that j > i to S, because that would only increase the value of the cut. Similarly, if i is the maximum index such that $${ \mathcal { B } } _ { i } \in S ^ { * }$$, then it's optimal to add every vertex Bj such that j < i to S.
Okay, so we can try finding minimum cut as a function F(x, y) — value of the cut if we choose S as the union of x first vertices in A and y first vertices in B.
To find its minimum, let's rewrite it as F(x, y) = F1(x) + F2(y) + F3(x, y), where F1(x) is the sum of capacities of edges added to the cut in part A (it doesn't depend on part B), F2(y) is the sum of capacities added to the cut from part B, and F3(x, y) is the sum of capacities added to the cut by edges going from A to B.
These functions can be denoted this way:
• F1(x) = 0 if x = n; otherwise F1(x) is the capacity of the edge going from Ax to Ax + 1;
• F2(y) = 0 if y = 0; otherwise F2(y) is the capacity of the edge going from By to By + 1;
• F3(x, y) is the sum of capacities over all edges Ai → Bj such that i ≤ x and j > y.
Since only the values of F1 are not fixed, we can solve this problem with the following algorithm:
1. For each x (1 ≤ x ≤ n), find the minimum possible sum of F2(y) + F3(x, y). Let's denote this as best(x), and let's denote T(x) = F1(x) + best(x);
2. Build a segment tree that allows to get minimum value and modify a single value over the values of T(x). When we need to change capacity of an edge, we add the difference between new and old capacities to T(x); and to calculate the maximum flow, we query minimum over the whole tree.
But how can we calculate the values of best(x)? We can do it using another segment tree that allows to query minimum on segment and add some value to the segment. First of all, let's set x = 0 and build this segment tree over values of F2(y) + F3(x, y). The value of F2(y) is fixed for given y, so it is not modified; the value of F3(x, y) is initially 0 since when x = 0, there are no vertices belonging to S in the part A.
And then we calculate the values of best(x) one by one. When we increase x, we need to process all edges leading from Ax to part B. When we process an edge leading to vertex Bi with capacity c, we have to add c to every value of F3(x, y) such that i > y (since if i > y, then $$B_i \notin S$$), and this can be performed by addition on segment in the segment tree. After processing each edge leading from Ax to part B, we can query best(x) as the minimum value in the segment tree.
Time complexity of this solution is $${ \mathcal { O } } \left( ( n + m + q ) \log n \right)$$.