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*<sub class="lower-index">*i*</sub>, and *i*-th vertex of part *B* is denoted as *B*<sub class="lower-index">*i*</sub>.

For each index *i* (1 ≤ *i* &lt; *n*) there is a directed edge from vertex *A*<sub class="lower-index">*i*</sub> to vertex *A*<sub class="lower-index">*i* + 1</sub>, and from *B*<sub class="lower-index">*i*</sub> to *B*<sub class="lower-index">*i* + 1</sub>, 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*<sub class="lower-index">1</sub> to *B*<sub class="lower-index">*n*</sub> in this network. Capacities of edges connecting *A*<sub class="lower-index">*i*</sub> to *A*<sub class="lower-index">*i* + 1</sub> 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<sup class="upper-index">5</sup>, 0 ≤ *q* ≤ 2·10<sup class="upper-index">5</sup>) — 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*<sub class="lower-index">*i*</sub> and *y*<sub class="lower-index">*i*</sub> denoting that the edge from *A*<sub class="lower-index">*i*</sub> to *A*<sub class="lower-index">*i* + 1</sub> has capacity *x*<sub class="lower-index">*i*</sub> and the edge from *B*<sub class="lower-index">*i*</sub> to *B*<sub class="lower-index">*i* + 1</sub> has capacity *y*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).

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*<sub class="lower-index">*x*</sub> to *B*<sub class="lower-index">*y*</sub> with capacity *z* (1 ≤ *x*, *y* ≤ *n*, 1 ≤ *z* ≤ 10<sup class="upper-index">9</sup>). There might be multiple edges from *A*<sub class="lower-index">*x*</sub> to *B*<sub class="lower-index">*y*</sub>.

And then *q* lines follow, describing a sequence of changes to the network. *i*-th line contains two integers *v*<sub class="lower-index">*i*</sub> and *w*<sub class="lower-index">*i*</sub>, denoting that the capacity of the edge from *A*<sub class="lower-index">*v*<sub class="lower-index">*i*</sub></sub> to *A*<sub class="lower-index">*v*<sub class="lower-index">*i*</sub> + 1</sub> is set to *w*<sub class="lower-index">*i*</sub> (1 ≤ *v*<sub class="lower-index">*i*</sub> &lt; *n*, 1 ≤ *w*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
This is the original network in the example:
4 3 2
1 2
3 4
5 6
2 2 7
1 4 8
4 3 9
1 100
2 100
9
14
14
10 10 10
291546518 199012865
327731857 137263959
145140225 631959974
559674936 815057131
677050070 949982094
839693202 160045764
967872826 489258292
706535160 594950620
230389718 274785590
1 10 861488983
7 10 994974516
4 3 117635148
6 2 167777067
5 7 445100727
2 1 921884141
7 7 959090371
7 10 181366040
10 7 81752829
6 7 936166852
3 990769845
4 35744486
9 546990449
7 359218204
7 77668723
8 653500720
6 5995747
5 383604942
3 184831761
7 149619462
1143893167
1153035501
1057279233
1057279233
1057279233
1057279233
1057279233
1057279233
1057279233
1057279233
1057279233
import heapq
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    x, y, s = [0] * (2 * m), [0] * m, [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        u, v, w = map(int, input().split())
        s[u + 2] += 1
        x[i], x[i + 1] = u, v
        y[i >> 1] = w
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G, W = [0] * m, [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i >> 1]
        s[j] += 1
    return G, W, s

def f(i):
    if not lazy[i]:
        return
    tree[i] += lazy[i]
    if i < l1:
        lazy[i << 1] += lazy[i]
        lazy[i << 1 ^ 1] += lazy[i]
    lazy[i] = 0
    return

def update(l, r, s):
    q, ll, rr, i = [1], [0], [l1 - 1], 0
    while len(q) ^ i:
        j = q[i]
        l0, r0 = ll[i], rr[i]
        if l <= l0 and r0 <= r:
            if s:
                lazy[j] += s
            f(j)
            i += 1
            continue
        f(j)
        m0 = (l0 + r0) >> 1
        if l <= m0 and l0 <= r:
            q.append(j << 1)
            ll.append(l0)
            rr.append(m0)
        if l <= r0 and m0 + 1 <= r:
            q.append(j << 1 ^ 1)
            ll.append(m0 + 1)
            rr.append(r0)
        i += 1
    for i in q[::-1]:
        if i < l1:
            j, k = i << 1, i << 1 ^ 1
            f(j)
            f(k)
            tree[i] = min(tree[j], tree[k])
    return
 
def get_min(s, t):
    update(s, t, 0)
    s += l1
    t += l1
    ans = inf
    while s <= t:
        if s % 2:
            ans = min(ans, tree[s])
            s += 1
        s >>= 1
        if not t % 2:
            ans = min(ans, tree[t])
            t -= 1
        t >>= 1
    return ans

n, m, q = map(int, input().split())
a, b = [0] * (n + 1), [0] * n
for i in range(1, n):
    x, y = map(int, input().split())
    a[i], b[i] = x, y
G, W, s0 = make_graph(n, m)
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
inf = pow(10, 15) + 1
tree, lazy = [inf] * l2, [0] * l2
mi = inf
for i in range(n - 1, -1, -1):
    mi = min(mi, b[i])
    tree[i + l1] = mi
for i in range(l1 - 1, 0, -1):
    tree[i] = min(tree[2 * i], tree[2 * i + 1])
c = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(s0[i], s0[i + 1]):
        update(0, G[j] - 1, W[j])
    c[i] = tree[1]
h = []
for i in range(1, n + 1):
    heapq.heappush(h, (a[i] + c[i], i))
ans = [h[0][0]]
for _ in range(q):
    v, w = map(int, input().split())
    heapq.heappush(h, (w + c[v], v))
    a[v] = w
    while (a[h[0][1]] + c[h[0][1]]) ^ h[0][0]:
        heapq.heappop(h)
    ans0 = h[0][0]
    ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))