题目描述

众所周知，波托科兰迪亚由 $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$。

2 1 1
3 2
2 1 4
1 6

4

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

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$ $\rightarrow$ $3$ $\rightarrow$ $2$）。

$$\begin{array}{|c|c|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{n, m} & \textbf{s} & \textbf{额外限制} & \textbf{额外限制 2} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & m = 2 \cdot (n - 1) & s = 1 & 对于任意\ 1 \le i < n & t_1 = 1，特殊性质\ A& 4 \\ & 1 \le n \le 1000 & & 存在连接城市\ i\ 与\ i + 1\ 的道路 & & \\ \hline \rule{0pt}{1.5em} 2 & m = 2 \cdot (n - 1) & s = 1 & 对于任意\ 1 \le i < n & 特殊性质\ A & 4 \\ & 1 \le n \le 1000 & & 存在连接城市\ i\ 与\ i + 1\ 的道路 & & \\ \hline \rule{0pt}{1.5em} 3 & m = 2 \cdot (n - 1) & s = 1 & 从任意城市可以到达任意其他城市 & 特殊性质\ A & 7 \\ & 1 \le n \le 1000 & & & & \\ \hline \rule{0pt}{1.5em} 4 & 1 \le n \le 1000 & s = 1 & - & 特殊性质\ A & 12 \\ & 0 \le m \le 4000 & & & & \\ \hline \rule{0pt}{1.5em} 5 & 1 \le n \le 10^5 & s = 1 & 所有\ w\ 值等于 \ 1 & 特殊性质\ A & 7 \\ & 0 \le m \le 4 \cdot 10^5 & & & & \\ \hline \rule{0pt}{1.5em} 6 & 1 \le n \le 10^5 & s = 1 & - & 特殊性质\ A & 10 \\ & 0 \le m \le 4 \cdot 10^5 & & & & \\ \hline \rule{0pt}{1.5em} 7 & 1 \le n \le 10^5 & 1 \le s \le 3 & - & - & 10 \\ & 0 \le m \le 4 \cdot 10^5 & & & & \\ \hline \rule{0pt}{1.5em} 8 & 1 \le n \le 1000 & 1 \le s \le 10 & - & - & 9 \\ & 0 \le m \le 4000 & & & & \\ \hline \rule{0pt}{1.5em} 9 & 1 \le n \le 10^5 & 1 \le s \le 10 & - & - & 9 \\ & 0 \le m \le 6 \cdot 10^5 & & & & \\ \hline \rule{0pt}{1.5em} 10 & 1 \le n \le 10^5 & 1 \le s \le 14 & - & - & 14 \\ & 0 \le m \le 6 \cdot 10^5 & & & & \\ \hline \rule{0pt}{1.5em} 11 & 1 \le n \le 10^5 & 1 \le s \le 18 & - & - & 14 \\ & 0 \le m \le 6 \cdot 10^5 & & & & \\ \hline \end{array}$$

特殊性质 A：对于任何一条从城市 $u$ 到城市 $v$ 的道路，都存在一条从城市 $v$ 到城市 $u$ 的道路，并且这两条道路的权重 $w$ 相等。

:::align{center} :::

翻译由 DeepSeek V3 完成