Bobo 有 $n$ 个球和 $n$ 个盒子，它们都被方便地标记为 $1, 2, \dots, n$。最初，第 $i$ 个球的美观度为 $w_i$。

他想把球放入盒子中。不幸的是，这并不总是可行的。Bobo 得到了 $m$ 条信息。第 $i$ 条信息 $(a_i, b_i)$ 表示第 $a_i$ 个球可以放入第 $b_i$ 个盒子中。由于一个盒子最多只能容纳一个球，Bobo 想要最大化放入盒子中的球的总美观度。

然而，情况是多变的。共有 $q$ 次修改 $(k_i, v_i)$，意味着第 $k_i$ 个球的美观度变为了 $v_i$。Bobo 想知道每次修改后最大总美观度是多少。注意，他可以随意重新安排球的放置。

输入格式

第一行包含 3 个整数 $n, m, q$ ($1 \le n, m \le 2 \times 10^5, 1 \le q \le 500$)。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($|w_i| \le 10^4$)。

接下来的 $m$ 行中，第 $i$ 行包含 2 个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)。

最后 $q$ 行中，第 $i$ 行包含 2 个整数 $k_i, v_i$ ($1 \le k_i \le n, |v_i| \le 10^4$)。

输出格式

输出 $q$ 个整数，表示每次修改后的最大总美观度。

样例

输入 1

2 2 1
5 8
1 1
2 1
1 9

输出 1

9

输入 2

3 3 3
1 2 4
1 1
2 2
3 3
1 2
2 4
3 8

输出 2

8
10
14