После того, как человечество нашло и обосновалось на новой планете, пригодной для жизни, возник вопрос, какую валюту использовать. После долгих дискуссий решили, что нужно использовать биткоин как основную валюту вселенной.
Это оказалось отличной новостью для Алисы, чей дедушка начал майнить биткоин еще в 2013, и накопил достаточно много. К сожалению, когда вы платите за что-то в биткоинах, все могут видеть, какая сумма у вас находится на данном биткоин-кошельке.
Это испугало Алису, поэтому она решила разделить все имеющиеся у нее биткоины по нескольким кошелькам так, чтобы в каждом кошельке было не более чем $$$x$$$ сатоши (1 биткоин = $$$10^8$$$ сатоши). Она может бесплатно создавать новые кошельки и будет платить по $$$f$$$ сатоши за перевод некоторого количества биткоинов на новый кошелек. Эта плата списывается с кошелька, с которого выполняется перевод. Вычислите для Алисы, сколько она должна заплатить за переводы, чтобы достичь своей цели.
Первая строка содержит одно целое число $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) — число кошельков, имеющихся сейчас у Алисы.
Следующая строка содержит $$$N$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — количества сатоши на каждом из кошельков.
Последняя строка содержит два целых числа $$$x$$$ и $$$f$$$ ($$$1 \leq f < x \leq 10^9$$$) — максимальное количество сатоши на одном кошельке, которое Алиса хочет получить, и стоимость одного перевода.
Выведите одно целое число — минимальная суммарная стоимость переводов в сатоши, необходимая для достижения цели Алисы.
3
13 7 6
6 2
4
В примере Алиса может сделать два перевода по следующей схеме:
0. 13 7 6 (начальное состояние)
1. 6 7 6 5 (создать новый кошелек и перевести 5 сатоши с первого кошелька)
2. 6 4 6 5 1 (создать новый кошелек и перевести 1 сатоши со второго кошелька)
Так как стоимость перевода равна 2 сатоши, суммарная стоимость равна 4 сатоши.
Название |
---|