说明

钰钰有一个环游世界的梦想，可是疫情让她的梦想破灭了，钰钰很难过，钰钰不想说话。

上帝听到了钰钰的心声，把她送到了异世界，祂告诉钰钰，在这里从一个城市传送到另外一个城市只需要经过传送门，传送门是不收费且不耗费时间的，你只需要为你的吃喝玩乐付出时间和金钱。钰钰可以选择任何一个城市作为起点（只能选择一次），同时每个城市只能游玩一次（但你可以路过多次），如果她能够在一定时间内花费掉m金钱，她就可以永远留在这个世界生活。

钰钰很心动，但她的数学学的不是很好，你能帮忙告诉她，她最少用多少时间就能够花费m金钱吗？

ps：到达一个城市并不一定要吃喝玩乐。

输入格式

第一行是三个数字n（1<=n<=10）和m(1<=m<=100000000），k（0<=k<=20），代表共有n个城市(编号从1开始)和至少要花费的金钱为m,以及异世界中共有k组双向传送门；

第二行共有n的数字x1，x2......xn，xi（1<=xi<=100000）代表到第i个城市吃喝玩乐的花费；

第三行共有n的数字y1，y2......yn，yi（1<=yi<=100000000）代表到第i个城市吃喝玩乐所需的时间；

接下来k行每行有两个数字w,v，代表编号为w的城市到编号为v的城市之间有一组双向传送门。

输出格式

输出一共一行

如果钰钰可以花费足够的金钱，输出“YES”并空一格输出最短时间；

如果不可以，输出“NO”。

样例

1 4 0
5
2

YES 2

样例

1 5 0
1
4

NO

样例

4 10 2
9 3 3 4
1 3 3 4
2 3
3 4

YES 10

提示

第一个样例从第一个城市出发即可；

第二个样例走遍所有城市也不能达到目标；

第三个样例路径为2—3—4，用最少时间花费10金钱。