問題文
在这个世界上,有M位魔法师,他们通过从魔法石中获得魔力来使用魔法。
魔力可以在人与人之间传递,但可以传递的数量是固定的,因为每个人彼此兼容,并且在传递魔力方面都有长处和短处。
魔力从魔石中涌出,没有限制,所以只要靠近魔石,就可以使用任何你想要的魔法,想要多少魔力就可以获得多少。
而且,巫师无法积累魔力。
亚丝娜想要洗澡,但她需要魔力来加热浴缸。
不幸的是,亚丝娜的家距离魔石很远。
其他人慷慨地给我魔力,所以我决定让别人给我他们的魔力,但我不知道我能得到多少魔力。
你会得到你可以走的路线以及你想要使用的魔法所需的魔力,所以如果你想烧水,就输出“是”,否则输出“否”。
入力
给你N条路线,巫师人数M,煮个澡所需的魔力P,魔法石附近巫师的数量G,魔法石附近巫师的列表,以及魔法师之间转移魔力的路线列表。
每个巫师都有一个编号,而亚丝娜的编号是0。
并且,对于每个巫师x,x能够转移的魔力总量小于或等于x已经接收的魔力总量。
输入按以下格式给出:
N M P G
L_0 ・・・ L_{G-1}
from_0 to_0 cap_0
・
・
・
・
from_{N-1} to_{N-1} cap_{N-1}
L_0 … L_{G-1}是魔法石附近魔法师的编号。
from_i、to_i、 cap_i分别是,
编号为from_i的魔术师to_i可以交给负责的魔法师的最大魔力是cap_i。
制約
输入时,所有变量均为整数。此外,还满足以下约束条件。
当
- 1≦N≦500
- 1≦M≦100
- 0≦G≦10
- 0≦P≦1000
- 0≦from_i,to_i<M
- 1≦cap_i≦1000
- i≠j当时L_i ≠ L_j。
还有全部
关于i关于L_i≠0。
- 全部i,
当我输入from_i≠to_i。
- 任何0≦i<j<N,
您可以获得(from_i,to_i)≠(from_j,to_j)
部分点
由于上述限制,
通过正确回答一些测试用例(包括
from_i - 1 = to_i
),您可以获得 40 分。
出力
如果亚丝娜能够接收到的魔力大于煮澡所需的魔力,则输出“Yes”,否则输出“No”一行。
入力例 3
4 5 100 2
3 4
1 0 200
2 1 50
3 2 100
4 2 100