荒芜的海洋

题目背景

在一个渺远的海洋中,一场世纪大战级别的游戏上演了。 感谢 [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”,并在下一行输出最多能找到多少奖赏。

输入输出样例

输入样例 #1

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

输出样例 #1

Yes
3741

输入样例 #2

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

输出样例 #2

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) ![](https://cdn.luogu.com.cn/upload/pic/14497.png) ![](https://cdn.luogu.com.cn/upload/pic/14498.png) By [Ebola](https://www.luogu.org/space/show?uid=20158)