CF1046F Splitting money

题目描述

爱丽丝有 $n$ 个账户,为了使自己的财产更分散些,她决定拆分自己的账户,把一些账户中的钱转入新账户,使每个账户中的钱数都不超过 $x$ 个单位货币。每一次转账都需要花费 $f$ 个单位货币的手续费。现在她想知道为了实现她的目标,她至少需要支付多少手续费。

输入格式

第一行有一个整数 $n(1 \le n \le 2 \times10^5)$,代表原来账户的个数。 第二行有 $n$ 个整数 $a_i(1 \le a_i \le 10^9)$,代表爱丽丝原本账户的钱数。 第三行两个整数 $x,f (1 \le f

输出格式

一行一个整数,代表爱丽丝的最少手续费。

说明/提示

爱丽丝转账的最优转账过程: 0. 13 7 6 (开始状态) 1. 6 7 6 5 (将 $5$ 个单位货币从第一个账户转向新账户,并且花费 $2$ 个单位货币的手续费) 2. 6 4 6 5 1 (将 $1$ 个单位货币从第二个账户转向新账户,也花费两个单位货币的手续费) 两次转账,总手续费为 $4$ 个单位货币。