CF903G.Yet Another Maxflow Problem

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 A__i, and i-th vertex of part B is denoted as B__i.

For each index i (1 ≤ i < n) there is a directed edge from vertex A__i to vertex A__i + 1, and from B__i to B__i + 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 _A_1 to B__n in this network. Capacities of edges connecting A__i to A__i + 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.

在本题中，你需要处理一种非常特殊的网络。

该网络由两部分组成：部分 A 和部分 B。每部分均包含 n 个顶点；部分 A 的第 i 个顶点记为 A__i，部分 B 的第 i 个顶点记为 B__i。

对每个下标 i（1 ≤ i < n），存在一条从顶点 A__i 指向顶点 A__i + 1 的有向边，以及一条从 B__i 指向 B__i + 1 的有向边。这些边的容量在输入中给出。此外，还可能存在若干条从部分 A 指向部分 B 的有向边（但绝不存在从 B 指向 A 的边）。

你需要计算该网络中从 _A_₁ 到 B__n 的最大流值。连接 A__i 与 A__i + 1 的边的容量有时会发生变化，你还需要在这些变化发生后动态维护最大流值。除此之外，网络结构是固定的（即部分 B 不发生变化，从 A 到 B 的边不发生变化，且不进行任何边的插入或删除操作）。

请参阅示例及说明，以更深入地理解该网络的结构。

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 x__i and y__i denoting that the edge from A__i to A__i + 1 has capacity x__i and the edge from B__i to B__i + 1 has capacity y__i (1 ≤ x__i, y__i ≤ 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 A__x to B__y with capacity z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109). There might be multiple edges from A__x to B__y.

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

第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n, m \leq 2 \cdot 10^5$，$0 \leq q \leq 2 \cdot 10^5$），分别表示两部分中的顶点数、从 $A$ 到 $B$ 的边数以及修改操作的次数。

接下来是 $n-1$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示从 $A_i$ 到 $A_{i+1}$ 的边容量为 $x_i$，从 $B_i$ 到 $B_{i+1}$ 的边容量为 $y_i$（$1 \leq x_i, y_i \leq 10^9$）。

接下来是 $m$ 行，描述从 $A$ 到 $B$ 的边。每行包含三个整数 $x$、$y$ 和 $z$，表示一条从 $A_x$ 到 $B_y$、容量为 $z$ 的边（$1 \leq x, y \leq n$，$1 \leq z \leq 10^9$）。从 $A_x$ 到 $B_y$ 可能存在多条边。

最后是 $q$ 行，描述对网络的一系列修改操作。第 $i$ 行包含两个整数 $v_i$ 和 $w_i$，表示将从 $A_{v_i}$ 到 $A_{v_i+1}$ 的边的容量设置为 $w_i$（$1 \leq v_i < n$，$1 \leq w_i \leq 10^9$）。

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.

首先，输出原始网络中的最大流值。然后输出 q 个整数，其中第 i 个整数必须等于执行第 i 次修改后的最大流值。

This is the original network in the example:

这是示例中的原始网络：