背景

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

感谢 lsq 本人参与验题

题目描述

这块海洋上有 $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”，并在下一行输出最多能找到多少奖赏。

4 6 3 2
16 37 22 24 
1 4 25
1 1 23
4 1 20
3 1 47
1 1 18
3 3 24
213 1
174 2
62 4
1493 3
2632 4

Yes
3741

4 2 3 2
16 37 22 24
1 4 25
1 3 12
213 1
174 3
62 4
1493 2
2632 4

No
1

提示

对于 $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