在这个问题中,您将不得不处理一个非常特殊的网络。
网络由两部分组成:A部分和B部分。每个部分由n个顶点组成; A 部分的第 i 个顶点表示为 Ai,B 部分的第 i 个顶点表示为 Bi。
对于每个索引 i (1 ≤ i < n),分别存在从顶点 Ai 到顶点 Ai + 1 以及从 Bi 到 Bi + 1 的有向边。这些边的容量在输入中给出。此外,可能存在多个从 A 部分到 B 部分(但绝不会从 B 到 A)的有向边。
您必须计算该网络中从 A1 到 Bn 的最大流量值。连接 Ai 到 Ai + 1 的边的容量有时可能会发生变化,并且您还必须在这些变化后保持最大流量值。除此之外,网络是固定的(B 部分没有变化,从 A 到 B 的边没有变化,也没有边插入或删除)。
看一下示例和注释可以更好地理解网络的结构。
输入
第一行包含三个整数 n、m 和 q (2 ≤ n, m ≤ 2·105, 0 ≤ q ≤ 2·105) — 分别是每个部分的顶点数、从 A 到 B 的边数和变化数。
接下来是 n - 1 行,第 i 行包含两个整数 xi 和 yi,表示从 Ai 到 Ai + 1 的边的容量为 xi,从 Bi 到 Bi + 1 的边的容量为 yi (1 ≤ xi, yi ≤ 109)。
接下来是 m 行,描述从 A 到 B 的边。每行包含三个整数 x、y 和 z,表示从 Ax 到 By 的边,容量为 z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109)。从 Ax 到 By 可能有多条边。
接下来是 q 行,描述网络的一系列更改。第i行包含两个整数vi和wi,表示从Avi到Avi + 1的边的容量设置为wi(1≤vi<n,1≤wi≤109)。
输出
首先打印原网络中的最大流量值。然后打印q个整数,其中第i个整数必须等于第i次更改后的最大流量值。
示例
输入 #1
4 3 2 1 2 3 4 5 6 2 2 7 1 4 8 4 3 9 1 100 2 100
输出 #1
9 14 14
注意
这是示例中的原始网络: