Warriors And Dragons

2 secs 1024 MB
uruzunyaa's icon uruzunyaa

問題文

村の戦士 NN 人でドラゴンに一斉攻撃を行います。
一斉攻撃で倒せなかった場合、ドラゴンの討伐に失敗します。

ドラゴンの防御力は DD であり、体力は HH です。
村の ii 人目(1iN)( 1 \leq i \leq N )の戦士の攻撃力は AiA_iです。

あなたは村の皆を守るため、ある魔法を使用しました。
その魔法は村の戦士全員の攻撃力を KK 倍する魔法です。

戦士一人の攻撃が、ドラゴンに対して与えるダメージは、以下のルールに従って計算されます。

  • 攻撃力が防御力より大きい場合、攻撃力と防御力の差のダメージとなる
  • 攻撃力が防御力より大きくない場合、11 のダメージとなる

ドラゴンの討伐に必要な KK の値として最小の正整数を 11 行に出力してください。

制約

  • 1N1051 \leq N \leq 10^5
  • 1D,H1091 \leq D,H \leq 10^9
  • 1Ai1081 \leq A_i \leq 10^8 (1iN)( 1 \leq i \leq N )

入力

入力はすべて整数である。

NN DD HH
A1A_1 A2A_2 ... AN A_N

出力

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

入出力例

入力例1
4 9 16
2 3 5 6
出力例1
3

K=3K=3 の場合、それぞれの攻撃力は6,9,15,18{6,9,15,18}となり、ドラゴンに与えるダメージは1+1+6+9=171+1+6+9=17となります。 17>=1617>=16 なため、ドラゴンを倒すことが出来ます。
22 以下で条件を達成する事は出来ないため、K=3K=3 が最小となります。

入力例2
1 1 1
20
出力例2
1

魔法を使わずともドラゴンを倒す事ができます。 KK は正整数なため 11 を出力します。

提出


Go (1.21)