题目描述

众所周知，波托科兰迪亚由 $n$ 座城市组成，城市之间有 $m$ 条单向道路。城市编号为 $1$ 到 $n$。编号为 $i$ 的城市中有 $p_i$ 袋土豆。对于每条道路，已知一个整数 $w_i$，表示哥萨克沿这条道路搬运一袋土豆所需的时间。不同道路的 $w$ 值可能不同。可以认为每座城市中都有极大量的哥萨克，因此任意数量的土豆袋都可以同时搬运。

哥萨克·乌斯得知，很快波托科兰迪亚将出现一种会毁坏土豆的病毒。为了保护收成，哥萨克们准备把土豆藏进地堡中。

全国共有 $s$ 个地堡，编号为 $1$ 到 $s$。编号为 $i$ 的地堡位于城市 $t_i$，最多可以保存 $c_i$ 袋土豆，使其免受病毒破坏。

现在，哥萨克想知道哥萨克们最少需要多少时间才能把所有土豆袋藏进地堡。请帮助他完成这个任务。

输入格式

第一行包含三个整数 $n,m,s$（$1\le n\le 10^5$，$0\le m\le 6\cdot 10^5$，$1\le s\le 18$），分别表示波托科兰迪亚中的城市数、道路数和地堡数。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$0\le p_i\le 10^9$），表示各城市中的土豆袋数。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$（$1\le u_i,v_i\le n$，$u_i\ne v_i$，$1\le w_i\le 10^9$），表示一条道路以及搬运一袋土豆通过该道路所需的时间。编号为 $i$ 的道路允许从城市 $u_i$ 移动到城市 $v_i$。保证对任意 $u_i,v_i$，至多存在一条从 $u_i$ 到 $v_i$ 的道路。

接下来 $s$ 行，每行包含两个整数 $t_i,c_i$（$1\le t_i\le n$，$1\le c_i\le 10^9$），表示对应地堡所在城市以及该地堡最多能保存的土豆袋数。

输出格式

输出一个整数，表示哥萨克们能把所有土豆袋藏进地堡所需的最短时间。如果无法把所有土豆袋都藏入地堡，则输出 $-1$。

样例

样例 1

2 1 1
3 2
2 1 4
1 6

4

样例 2

4 6 2
2 0 0 2
2 1 6
3 1 2
3 2 3
1 3 4
4 3 4
2 4 6
3 2
2 2

7

样例 3

7 10 3
0 1 1 1 1 0 2
2 1 1
3 2 1
3 1 1
6 4 5
4 5 9
3 4 1
7 6 10
5 7 3
6 5 3
4 3 1
6 5
1 1
2 1

22

样例解释

第一个样例中，可以把所有土豆袋都藏进地堡。为此，只需从编号为 $2$ 的城市向编号为 $1$ 的城市搬运两袋土豆。

第二个样例中，需要在每个地堡中各藏 $2$ 袋土豆。为此，只需从编号为 $1$ 的城市向编号为 $3$ 的城市搬运两袋土豆，并从编号为 $4$ 的城市向编号为 $2$ 的城市搬运两袋土豆（后者最好走路径 $4\to 3\to 2$）。

计分方式

原题计分表如下图所示：

文字化整理如下：