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](https://en.wikipedia.org/wiki/Maximum_flow_problem) 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.
## Input
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).
## Output
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.
[samples]
## Note
This is the original network in the example:
<center></center>
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ denote the number of vertices in each part, the number of $ A \to B $ edges, and the number of updates, respectively.
Let $ A = \{A_1, A_2, \dots, A_n\} $ and $ B = \{B_1, B_2, \dots, B_n\} $ be the vertex sets of the two parts.
For $ i \in \{1, \dots, n-1\} $:
- Let $ c_{A,i} \in \mathbb{R}^+ $ denote the capacity of edge $ A_i \to A_{i+1} $.
- Let $ c_{B,i} \in \mathbb{R}^+ $ denote the capacity of edge $ B_i \to B_{i+1} $.
Let $ E_{AB} \subseteq \{1,\dots,n\} \times \{1,\dots,n\} \times \mathbb{R}^+ $ be the multiset of directed edges from $ A $ to $ B $, where each element $ (x, y, z) \in E_{AB} $ represents an edge $ A_x \to B_y $ with capacity $ z $.
Let $ \mathcal{G} = (V, E) $ be the directed flow network with:
- Vertex set $ V = A \cup B $,
- Edge set $ E = \bigcup_{i=1}^{n-1} \{ (A_i, A_{i+1}), (B_i, B_{i+1}) \} \cup E_{AB} $.
**Constraints**
1. $ 2 \le n, m \le 2 \cdot 10^5 $, $ 0 \le q \le 2 \cdot 10^5 $
2. $ 1 \le c_{A,i}, c_{B,i} \le 10^9 $ for all $ i \in \{1, \dots, n-1\} $
3. For each $ (x, y, z) \in E_{AB} $: $ 1 \le x, y \le n $, $ 1 \le z \le 10^9 $
4. Updates: each update sets $ c_{A,v_i} \leftarrow w_i $ for $ 1 \le v_i < n $, $ 1 \le w_i \le 10^9 $
**Objective**
Compute the maximum flow from $ A_1 $ to $ B_n $ in $ \mathcal{G} $, and update it after each of the $ q $ capacity changes.
Let $ f_0 $ be the maximum flow in the initial network.
For each update $ i \in \{1, \dots, q\} $, let $ f_i $ be the maximum flow after the $ i $-th update.
Output $ f_0, f_1, \dots, f_q $.