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. The first line contains three integer numbers n , m and q ( 2 ≤ n , m ≤ 2·10 5 , 0 ≤ q ≤ 2·10 5 ) — 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 ≤ 10 9 ). 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 ≤ 10 9 ). 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 ≤ 10 9 ). Firstly, print the maximum flow value in the original network. Then print q integers, i -th of them must be equal