找到并搬到支持人类生命的新星球后,开始讨论应该使用哪种货币。经过长期谈判,最终选择比特币作为通用货币。
这对 Alice 来说是个好消息,她的祖父在 2013 年进入了比特币挖矿领域,多年来积累了很多比特币。不幸的是,当用比特币支付时,每个人都可以看到您的公共地址钱包中有多少比特币。
这让 Alice 很担心,所以她决定将她的比特币分割到多个不同的地址中,这样每个地址最多有 $$$x$$$ 聪(1 比特币 = $$$10^8$$$ 聪)。她可以免费创建新的公共地址钱包,并愿意为每笔交易支付 $$$f$$$ 聪费用,以确保可接受的转账速度。费用从发送交易的地址中扣除。告诉爱丽丝她需要支付多少聪才能实现她的目标。
输入
第一行包含数字 $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) 代表 Alice 拥有的公共地址总数。
下一行包含 $$$N$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$),用一个空格分隔,代表 Alice 在她的公共地址中拥有多少聪。
最后一行包含两个数字 $$$x$$$, $$$f$$$ ($$$1 \leq f < x \leq 10^9$$$) 代表 Alice 在一个地址中可以拥有的最大聪数,以及她愿意为每笔交易支付的聪的费用。
输出
输出一个整数,代表爱丽丝为实现其目标而需要支付的总费用(以聪为单位)。
示例
输入 #1
3 13 7 6 6 2
输出 #1
4
注意
Alice 可以通过以下方式进行两笔交易:
0. 13 7 6(初始状态)
1. 6 7 6 5(创建新地址并从第一个公共地址转移5 satoshies)
2. 6 4 6 5 1(创建新地址并从第二个地址1 satoshi转账)
由于每笔交易的成本为 2 聪,因此总费用为 4。