题目来源

清北学堂入学考试题--2018/2/6精英班

题目描述

D公司最近生意十分火爆，于是他们决定租一个仓库来存放货物。经过评估D公司租借了一个大小为m的仓库。根据市场调查D公司知道了接下来n天的销售情况。每天早上公司可以选择是否进货，一次进货需要x的价格，可以进任意数量的货。为了保证仓库安全，每个货物都要有专业的保护工具，每天一个保护工具的使用费用为y。D公司想知道满足n天销售的情况下，最小的费用是多少。

输入

第一行四个数n,m,x,y 如题意描述
第二行n个数，表示每天的销量

输出

一个数表示最小的费用

输入样例

4 10 9 1
4 1 5 2

输出样例

21

样例解释

在第一天进5个，代价为9，卖出4个， 保护费为1
第二天直接卖出1个，保护费为0
第三天进7个，代价为9，卖出5个，保护费为2
第四天直接卖出两个。
一共为9+9+2+1 = 21

数据范围

30%的数据满足n<=10 m<=10
60%的数据满足 n<=100 m<=100
100%的数据满足 n<=5000 m<=1000000000 0<x<=10000000 0<y<=10000

限制

每个测试点2秒,内存限制256M