99991320 - [ABC063D] Widespread

通过次数

9

提交次数

37

Time Limit : 1 秒
Memory Limit : 128 MB

AtCoder Beginner Contest 063 D

当你在散步时,突然出现了 N 个魔物。每个魔物都有一个名为 体力 的值,第 i 个魔物出现时的体力为 h_i 。体力降至 0 或以下的魔物将立即消失。

幸运的是,您是一位熟练的魔法师,可以引爆并攻击魔物。每次爆炸都可以减少魔物的体力,如下所示:

  • 选择一个存活的魔物,以该魔物为中心引爆。中心爆炸的魔物的体力减少 A,其他魔物的体力分别减少 B。这里, A B 是预先确定的值,并且 A\ >\ B

为了消灭所有魔物,最少需要引爆多少次?

Input

  • 所有输入都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq B < A \leq 10^9
  • 1 \leq h_i \leq 10^9

输入格式如下所示:

N A B

h_1

h_2

:

h_N

Output

最少引爆次数。

Examples

Input

4 5 3
8
7
4
2

Output

2

Input

2 10 4
20
20

Output

4

Input

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

Output

800000000

Hint

Sample Explanation 1

以下のようにして、 2 回の爆発ですべての魔物を消し去ることができます。

  • まず、体力が 8 の魔物を中心に爆発を引き起こす。 4 体の魔物の体力はそれぞれ 3 , 4 , 1 , -1 となり、最後の魔物は消滅する。
  • 次に、残りの体力が 4 の魔物を中心に爆発を引き起こす。残っていた 3 体の魔物の体力はそれぞれ 0 , -1 , -2 となり、すべての魔物が消滅する。

Sample Explanation 2

それぞれの魔物を中心に 2 回ずつ、合計で 4 回の爆発を引き起こす必要があります。