题目背景

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

感谢 lsq 本人参与验题

题目描述

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

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<=200，m<=200，b<=a<=30

对于50% 的数据，满足n<=500，m<=800，b<=a<=100

对于100% 的数据，满足n<=1000，m<=15000，b<=a<=300，其余数据保证不会爆int(Pascal语言为longint)

By Ebola