H - お風呂は気持ちいい Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

この世界では魔法使いは、魔導石から魔力をもらって魔法をつかい、M人の魔法使いが存在します。
魔力は人から人へと渡すことができますが、人同士で相性があり、受け渡しの得手不得手もあるので、渡せる量は決まっています。
魔導石からは無制限に魔力が湧き出てくるので、魔導石の近くならばどんな魔法でも使うことができ、いくらでも魔力を得ることができます。
また、魔法使いは魔力を蓄積することはできません。

アスナさんは、お風呂に入りたいのですが、お風呂を沸かすためには魔力が必要です。
あいにく残念なことに、アスナさんの家は魔導石からは離れています。

他の人は気前よく魔力をくれるので、他の人に魔力を経由してもらうことにしましたが、どのぐらい魔力が得られるのかがわかりません。
経由できるルートと、使いたい魔法に必要な魔力が与えられるので、お風呂を沸かせるならば"Yes"そうでないならば"No"と出力してください。

入力

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"と一行で出力してください。

入力例 1

1 2 100 1
1
1 0 200

出力例 1

Yes

入力例 2

1 3 100 1
1
2 1 200

出力例 2

No

入力例 3

4 5 100 2
3 4
1 0 200
2 1 50
3 2 100
4 2 100

出力例 3

No