题目内容

一个数组代表河堤的高度，堤坝是等长、等宽的，现在需要在不超过最大预算的前提下，尽可能的加固河堤使最低高度，所有加固的土只能通过一定的成本来运输和填充。一辆车一次只能运输一定量的土，运输成本每次固定，一车土可以填入多个堤坝，填埋每个单位成本固定。求出在不超过给定预算成本的情况下，填埋后的所有河堤岸最低高度的最大值是多少。

输入描述

最大预算成本MaxCosts，$\left(1 \le MaxCosts \le 1000\,0000\,0000\right)$

每车最大载量MaxCapacity，$\left(1 \le MaxCapacity \le 100\right)$

每车单次运输成本TransportationCostPerShipment，

$\left(1 \le TransportationCostPerShipment \le 100\right)$

每个单位高度的土填埋成本UnitCost，$\left(1 \le UnitCost \le 100\right)$

河堤个数num，$\left(1 \le num \le 100000\right)$

河堤高度数据heights[]，空格分割，数据个数为num。

$\left(0 \le heights[i] \le 1000000\right)$

输出描述

预算成本内，可以加固的最低高度最大值。

注意，可提高预算情况下，最大值会超过加固前河堤最大高度。

样例1

输入：

100
10
5
2
5
1 2 5 3 4

输出：

11

解释：

最大预算成本100，每车最大载量10，单次运输成本为5，每个单位高度的土填埋成本是2，河堤线长度是5。

最优方案是成本内，所有河堤最低高度加固到11，总共土填埋成本为$(11-1 + 11-2 + 11-5 + 11-3 + 11-4) * 2=80$，运输成本是，需要4辆车拉取40个单位的土，运输成本为20，共计花费100，不超过最大预算成本。

如果所有河堤最低高度加固到12，总共土填埋成本为$(12-1 + 12-2 + 12-5 + 12-3 + 12-4) * 2=90$。运输成本是，需要5辆车拉取45个单位的土，运输成本为25，共计花费115，超过最大预算成本。

样例2

输入：

50
10
10
1
10
1 2 5 3 4 5 4 1 1 1

输出：

4

解释：

最大预算成本50，每车最大载量10，单次运输成本为10，每个单位高度的土填埋成本是1，河堤线长度是10。

最优方案是成本内，所有河堤最低高度加固到4，总共土填埋成本为$(4-1 + 4-2 + 4-3 + 4-1 + 4-1 + 4-1) * 1=15$，运输成本是，需要2辆车拉取15个单位的土，运输成本为20，共计花费35，不超过最大预算成本。

如果所有河堤最低高度加固到5，总共土填埋成本为$(5-1 + 5-2 + 5-3 + 5-4 + 5-4 + 5-1 + 5-1 + 5-1) * 1=23$，运输成本是，需要3辆车拉取23个单位的土，运输成本为30，共计花费53，超过最大预算成本。