P3593.第3题-搬砖
题目内容
又到了一年暑假，这次暑假小 D 准备去打工赚点零花钱，于是他来到了一个工地上，这里的工作要求他将 n 堆砖块(第 i 堆砖块共有 ai 块砖)从 a 处搬到 b 处，自己动手搬的话，用 x 秒的时间可以将一块砖从 a 处搬到 b 处，但这样会花费很长的时间，所以相关领导为工地配备了卡车。
通过使用卡车，可以用 v 秒的时间将一整堆砖块从 a 处搬到 b 处。
由于车辆油耗的存在，在完成工作之前最多只能用卡车搬运 K 堆砖块。
小 D 找到你，想请你帮他计算一下，在不间断地搬砖的情况下，他至少要用多少秒才能把 n 堆砖块全部搬到 b 处。
输入描述
第一行四个正整数 n,x,y 和 K(1≤K≤n≤40000，1≤x<y≤108) ，表示砖块堆数、手动搬所需时间、开车搬所需时间和卡车搬运次数。
第二行为 n 个正整数 a1,a2,...,an ，其中 ai 表示第 i 堆砖块个数为 ai(1≤ai≤105) 。
输出描述
输出一个正整数，表示把全部砖块搬到 b 处需要的最少时间。
样例1
输入
4 1 5 1
2 6 3 8
输出
16
说明
如果全部手动搬的话，这四堆搬完所需的时间分别为 2、6、3、8 ，由于可以使用一次卡车，所以用于搬运第四堆，这样每堆所需的时间分别为 2、6、3、5 ，总和为 16 ，为可达到的最小值。
