P4237 荒芜的海洋

在一个渺远的海洋中，一场世纪大战级别的游戏上演了。 感谢 [lsq](https://www.luogu.org/space/show?uid=26556) 本人参与验题

这块海洋上有 $n$ 个小岛，小岛有 $m$ 座石桥相连。有一些小岛上有 wzt 埋下的奖赏，它们非常诱人。它们的诱惑力用整数 $k_i$ 描述。而一些小岛上有 lsq 的雇佣兵，他们有一个价格，用整数 $b_i$ 描述。lsq 必须花钱，他的雇佣兵才会帮他寻找奖赏。 雇佣兵的价格并不会变。对于每一个雇佣兵，在寻找过程中，他会越过一座座的桥，这过程中，他的价格会 **加上他所经过的所有桥的长度** 。 遗憾的是，不只有桥的阻挡，每座岛上有许多猛兽，虽然雇佣兵们都英勇无比，但驱逐猛兽的过程会让人很不爽。因此，对于每一个雇佣兵，价格会 **加上他所经过的所有岛（包括出发岛）上的猛兽数量之和**。 lsq 了解这里的一切情况，他需要做出决策，即决定他的每个雇佣兵应该去找哪个奖赏。lsq 的目的是找到所有奖赏，并取得最大收益。每个雇佣兵只能雇佣一次。 收益的定义为： **所有奖赏的诱惑力减去 lsq 花的所有的钱**。 lsq 的决策异常艰难，于是只好请 ~~AK 过 NOI~~ 的你来帮忙。

第一行 $4$ 个数，$n$（小岛总数）,$m$（桥总数）,$a$（lsq 的雇佣兵总人数）,$b$（奖赏总数）。 接下来一行 $n$ 个数，表示每个小岛上的猛兽数量。 接下来 $m$ 行，每行三个数 $u,v,w$，表示 $u$ 号小岛与$v$ 号小岛之间有一座长度为 $w$ 的桥相连。 接下来 $a$ 行，每行两个数 $q_i,p_i$，表示 $i$ 号雇佣兵价格为 $q_i$，初始位置为 $p_i$ 号小岛。 接下来 $b$ 行，每行两个数 $k_i,q_i$，表示 $i$ 号奖赏的诱惑力为 $k_i$，位置为 $q_i$ 号小岛。

如果能找到所有奖赏，输出“Yes”，并在下一行输出能达到的最大满意度。 如果不能找到所有奖赏，输出“No”，并在下一行输出最多能找到多少奖赏。

对于 $30\%$ 的数据，满足 $n \le 200，m\le 200，b\le a\le 30$。 对于 $50\%$ 的数据，满足 $n \le 500，m\le 800，b\le a\le 100$。 对于 $100\%$ 的数据，满足 $n \le 1000，m\le 15000，b\le a\le 300$，其余数据保证不会爆 int(Pascal 语言为 longint)。   By [Ebola](https://www.luogu.org/space/show?uid=20158)