解题思路

核心建模

• 第 $i$ 堆若全手搬，耗时：$a_i \cdot x$

• 若用卡车，整堆耗时：$y$

• 对第 $i$ 堆，用车带来的收益（节省的时间）：

  $$\text{save}_i=\max(0,\,a_i\cdot x-y)$$

题目内容

又到了一年暑假，这次暑假小 $D$ 准备去打工赚点零花钱，于是他来到了一个工地上，这里的工作要求他将 $n$ 堆砖块(第 $i$ 堆砖块共有 $a_i$ 块砖)从 $a$ 处搬到 $b$ 处，自己动手搬的话，用 $x$ 秒的时间可以将一块砖从 $a$ 处搬到 $b$ 处，但这样会花费很长的时间，所以相关领导为工地配备了卡车。

通过使用卡车，可以用 $v$ 秒的时间将一整堆砖块从 $a$ 处搬到 $b$ 处。

由于车辆油耗的存在，在完成工作之前最多只能用卡车搬运 $K$ 堆砖块。

小 $D$ 找到你，想请你帮他计算一下，在不间断地搬砖的情况下，他至少要用多少秒才能把 $n$ 堆砖块全部搬到 $b$ 处。

输入描述

第一行四个正整数 $n,x,y$ 和 $K(1≤K≤n≤40000，1≤x<y≤10^8)$ ，表示砖块堆数、手动搬所需时间、开车搬所需时间和卡车搬运次数。

第二行为 $n$ 个正整数 $a_1, a_2,..., a_n$ ，其中 $a_i$ 表示第 $i$ 堆砖块个数为 $a_i(1≤a_i≤10^5)$ 。

输出描述

输出一个正整数，表示把全部砖块搬到 $b$ 处需要的最少时间。

样例1

输入

4 1 5 1
2 6 3 8

输出

16

说明

如果全部手动搬的话，这四堆搬完所需的时间分别为 $2、6、3、8$ ，由于可以使用一次卡车，所以用于搬运第四堆，这样每堆所需的时间分别为 $2、6、3、5$ ，总和为 $16$ ，为可达到的最小值。