D - Many Go Round

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100

問題文

ある日 S 君は環状の道路をドライブすることにした。

この環状道路には等間隔に休憩所があり、0 から M - 1 までの番号が振られている。
S 君は0番の休憩所からスタートし、0 → 1 → 2 → … → (M - 2) → (M - 1) → 0 → 1 → 2 → … と巡回する。

S 君の車は,燃料1リットルで休憩所を1つ進むことができる。
しかし燃料の補充の際は、あらかじめ用意した、補充量が a_1 , a_2 , a_3 ,…, a_{N-1} , a_{N} である N 個の燃料タンクから 1 つ以上選んで補充しなけらばならない。
燃料タンクは補充を行うと空になるため、同じ燃料タンクを2回以上選ぶことはできない。 この車は走り出すと燃料を使い切るまで止まらないため、ある特定の休憩所に停まりたい場合は、ぴったりそこで燃料が尽きるように補充する燃料タンクを選ばなければならない。

S 君は番号Lの休憩所で友人と待ち合わせをしており、車の燃料が0の状態で燃料タンクを複数選んで補充し、番号0の休憩所からスタートして番号Lの休憩所に停まりたい。
しかし環状道路をX周以上すると市の交通条例違反になってしまう。

S 君がX周以内に番号Lの休憩所に停まることができるような燃料タンクの選び方は存在するかどうかを判定せよ。

燃料の補充は最初の1回のみである。また、スタート直後は1周目と定義し、再び番号0の休憩所にたどり着いた時点で次の周回とする。

制約

  • 1 \leq N \leq 10000
  • 3 \leq M \leq 1000
  • 1 \leq L \leq M - 1
  • 2 \leq X \leq 10000
  • 1 \leq a_i \leq 10000

入力

入力は以下の形式で標準入力から与えられる。

N M L X
a_1 a_2 ... a_N

1 行目には、燃料タンクの数 N 、休憩所の個数 M 、目的の休憩所の番号 L 及び条例違反となる周回数 X が与えられる。

2 行目には、用意された N 個の燃料タンクそれぞれの補充量が正の整数で与えられる。a_ii 番目のタンクの補充量を示す。

出力

S 君が X 周以内に番号 L の休憩所に停まることができる場合は Yes を、停まることができない場合は No を出力せよ。


入力例 1

5 11 7 5
1 4 5 8 9

出力例 1

Yes

数字を組み合わせて 7(1 周目) を作ることはできない。

1 + 8 + 9 = 18 であり、1周 + 目的の番号(11+7 = 18) と等しくなるため 2 周目(\leq X = 5) に停まることができる。


入力例 2

5 5 3 2
1 4 5 9 12

出力例 2

No

数字を組み合わせて 3(1 周目), 8(2 週目) を作ることはできない。

1 + 12 = 13 であり、2 周 + 目的の番号 (10+3) と等しくなるため 3 周目で停まることができるが,X = 2 周を超えてしまっているため No。


入力例 3

5 10 3 100
1 4 7 10 14

出力例 3

No

どの組み合わせを選んでも3(1 周目), 13(2 周目), 23(3 周目), 33(4 周目) を作ることはできない。