A2566 | 荒芜的海洋

在一个渺远的海洋中，一场世纪大战级别的游戏上演了。

感谢 [lsq](https://www.luogu.org/space/show?uid=26556) 本人参与验题这块海洋上有n个小岛，小岛有m座石桥相连。有一些小岛上有wzt埋下的奖赏，它们非常诱人。它们的诱惑力用整数ki描述。而一些小岛上有lsq的雇佣兵，他们有一个价格，用整数bi描述。lsq必须花钱，他的雇佣兵才会帮他寻找奖赏。

雇佣兵的价格并不会变。对于每一个雇佣兵，在寻找过程中，他会越过一座座的桥，这过程中，他的价格会 **加上他所经过的所有桥的长度** 。

遗憾的是，不只有桥的阻挡，每座岛上有许多猛兽，虽然雇佣兵们都英勇无比，但驱逐猛兽的过程会让人很不爽。因此，对于每一个雇佣兵，价格会 **加上他所经过的所有岛（包括出发岛）上的猛兽数量之和**。

lsq了解这里的一切情况，他需要做出决策，即决定他的每个雇佣兵应该去找哪个奖赏。lsq的目的是找到所有奖赏，并取得最大收益。每个雇佣兵只能雇佣一次。

收益的定义为： **所有奖赏的诱惑力减去lsq花的所有的钱**

lsq的决策异常艰难，于是只好请 ~~AK过NOI~~ 的你来帮忙。

第一行4个数，n（小岛总数）,m（桥总数）,a（lsq的雇佣兵总人数）,b（奖赏总数）

接下来一行n个数，表示每个小岛上的猛兽数量

接下来m行，每行三个数u,v,w，表示u号小岛与v号小岛之间有一座长度为w的桥相连

接下来a行，每行两个数qi,pi，表示i号雇佣兵价格为qi，初始位置为pi号小岛

接下来b行，每行两个数ki,qi，表示i号奖赏的诱惑力为ki，位置为qi号小岛

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

如果不能找到所有奖赏，输出“No”，并在下一行输出最多能找到多少奖赏。