Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

flows

graphs

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Yet Another Maxflow Problem

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

Input

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*_{vi} to *A*_{vi + 1} is set to *w*_{i} (1 ≤ *v*_{i} < *n*, 1 ≤ *w*_{i} ≤ 10^{9}).

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.

Example

Input

4 3 2

1 2

3 4

5 6

2 2 7

1 4 8

4 3 9

1 100

2 100

Output

9

14

14

Note

This is the original network in the example:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2024 17:34:15 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|