問題文

福田さんは、NN 本のエナジードリンクを飲む計画を立てることにしました。

それぞれのエナジードリンクには Ai(1iN)A_i(1 \leq i \leq N) ミリグラムのカフェインが入っており、次のように振る舞います。

  • 初期時、福田さんの身体にカフェインは吸収されていない。
  • エナジードリンクを飲むと、AiA_i ミリグラムのカフェインが、福田さんの身体に吸収される。
  • エナジードリンクを飲んだ次の時間から、11 時間が進むごとに XX ミリグラムのカフェインが分解される。
  • カフェインが体内にある状態でエナジードリンクを飲むと、先に分解が行われてから吸収が行われる。

また、エナジードリンクを飲むときにも以下の制約があります。

  • 11 時間に飲めるエナジードリンクは最大で 11 本まで。
  • 11 本目から NN 本目まで、順番通りに飲まないといけない。

福田さんは、体内に YY ミリグラム以上のカフェインが吸収されている状態になると、急性カフェイン中毒で倒れてしまいます。 無事にすべてのエナジードリンクを飲み切るのは、最も速くて何時間目ですか?

制約

  • 1N1001 \leq N \leq 100
  • 0Ai1000 \leq A_i \leq 100
  • 1X1001 \leq X \leq 100
  • max(Ai)Y1000\max(A_i) \leq Y \leq 1000
  • 入力はすべて整数

入出力

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

入力
N X Y
A_1 A_2 ... A_N

答えを出力してください。

サンプル

入力例1
5 15 100
40 50 30 60 20
出力例1
8
  • 11 時間目、11 本目のエナジードリンクを飲んで、カフェイン量は 4040 ミリグラムになります。
  • 22 時間目、1515 ミリグラム分解され、22 本目のエナジードリンクを飲んで、カフェイン量は 7575 ミリグラムになります。
  • 33 時間目、1515 ミリグラム分解され、33 本目のエナジードリンクを飲んで、カフェイン量は 9090 ミリグラムになります。
  • 44 時間目、1515 ミリグラム分解され、カフェイン量は 7575 ミリグラムになります。
  • 55 時間目、1515 ミリグラム分解され、カフェイン量は 6060 ミリグラムになります。
  • 66 時間目、1515 ミリグラム分解され、カフェイン量は 4545 ミリグラムになります。
  • 77 時間目、1515 ミリグラム分解され、44 本目のエナジードリンクを飲んで、カフェイン量は 9090 ミリグラムになります。
  • 88 時間目、1515 ミリグラム分解され、55 本目のエナジードリンクを飲んで、カフェイン量は 9595 ミリグラムになります。 したがって、すべてのエナジードリンクを飲みきるには 88 時間が必要です。
入力例2
10 50 30
0 0 0 0 0 0 0 0 0 0
出力例2
10

カフェインが含まれないエナジードリンクを飲むこともあります。

提出


Go (1.21)