eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Волшебники и волки

Волшебники и волки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Однажды, прогуливаясь, Вы встретили n волков. У каждого волка есть свой параметр силы – здоровье. При встрече с волками, у i-го волка было h[i] единиц здоровья. Если у какого-то волка здоровье падает до 0 или ниже, то он умирает.

К счастью вы волшебник, который может создавать взрывы. Этими взрывами вы можете уменьшать здоровье волков. Одним взрывом здоровье волков можно уменьшать следующими способами:

Выбрав какого-либо живого волка, вы производите взрыв рядом с ним. В таком случае здоровье выбранного волка уменьшается на a единиц, а всех остальных на b единиц. a и b даны Вам изначально.

Какое минимальное количество взрывов нужно произвести, чтобы убить всех волков?

Вхідні дані

Первая строка содержит три числа n (1n10^5), a и b (1b < a10^9). В каждой из следующих n строк задано число h[i] (1h[i]10^9) - здоровье i-го волка.

Вихідні дані

Выведите минимальное количество взрывов, необходимых для уничтожения всех волков.

Объяснение

Тест 1.

  • Создадим взрыв рядом с волком со здоровьем 8. После взрыва здоровье у волков будет соответственно 3, 4, 1, -1.

  • Второй взрыв произведем рядом с волком со здоровьем равным 4. После второго взрыва все волки умрут.

Тест 2.

  • Чтобы убить всех волков, надо рядом с каждым из них произвести 2 взрыва, в итоге 4 взрыва. Более меньшим числом взрывов убить всех волков невозможно

Приклад

Вхідні дані #1
4 5 3
8
7
4
2
Вихідні дані #1
2
Вхідні дані #2
2 10 4
20
20
Вихідні дані #2
4
Вхідні дані #3
5 2 1
900000000
900000000
1000000000
1000000000
1000000000
Вихідні дані #3
800000000
Автор Рашад Маммадов, Абуталыб Намазов
Джерело Азербайджан 2019: Отборочный тур в старшую олимпийскую группу подготовки