题目内容

现有一段由若干个等长、等宽堤坝组成的河堤，其各处初始高度由数组 $heights[]$ 给出。为了提升整段河堤的防护能力，需要向高度不足的堤坝填土进行加固，并希望在总花费不超过最大预算成本 $MaxCosts$ 的条件下，使加固后所有堤坝中的最低高度尽可能高。

加固所使用的土需要通过车辆运输。每辆车一次最多能够运输 $MaxCapacity$ 个单位的土，每完成一次运输，都需要支付固定的单次运输成本 $TransportationCostPerShipment$。同一车运输的土可以分配并填入多个堤坝。

除运输费用外，实际填埋土方也会产生费用：每填埋 $1$ 个单位高度的土，需要支付固定成本 $UnitCost$。

因此，对任意目标最低高度，需要同时计算为所有低于该高度的堤坝补足高度所需的土方量、填埋成本以及对应的运输成本。总成本不得超过 $MaxCosts$。

请计算在给定预算范围内完成加固后，所有河堤岸能够达到的最低高度的最大值。

输入描述

输入包含6行：

最大预算成本 $MaxCosts$；

每车最大载量 $MaxCapacity$；

每车单次运输成本 $TransportationCostPerShipment$；

每填埋 $1$ 个单位高度的土所需成本 $UnitCost$；

河堤个数 $num$；

河堤高度数组 $heights[]$，各高度之间使用空格分隔，数据数量为 $num$。

输入数据保证：

输出描述

输出在总成本不超过最大预算成本 $MaxCosts$ 的前提下，所有河堤岸加固后能够达到的最低高度的最大值。

需要注意，当预算允许继续填土加固时，该最大值可能超过加固前河堤中的最大高度。

样例1

输入

100
5
10
2
3
1 10 20

输出

18

说明

目标高度为 18 时，低于 18 的堤坝是初始高度 1 和 10，分别需要填土 17 和 8，总土方量为 $17+8=25$。发车次数为 $\lceil 25/5 \rceil = 5$。总费用为 $25 \times 2 + 5 \times 10 = 100$，恰好不超过预算 100。

目标高度为 19 时，总土方量为 $18+9=27$，发车次数为 $\lceil 27/5 \rceil = 6$。总费用为 $27 \times 2 + 6 \times 10 = 114$，超过预算 100。

因此最大可达高度为 18。

样例2

输入

10
100
5
3
1
0

输出

1

说明

对于目标高度 $H$，唯一一段堤坝初始高度为 0，所需填土方量为 $H$。发车次数为 $\lceil \frac{H}{100} \rceil$，总费用为 $3H + 5\lceil \frac{H}{100} \rceil$。

当 $H=1$ 时，费用为 $3 \times 1 + 5 \times 1 = 8$，不超过预算 10。当 $H=2$ 时，费用为 $3 \times 2 + 5 \times 1 = 11$，超过预算 10。

因此最大可达高度为 1。

样例3

输入

1000
10
100
10
4
100 100 100 100

输出

112

说明

四段堤坝的初始高度均为 100。目标高度为 112 时，每段需要填土 12，总土方量为 $4 \times 12 = 48$。发车次数为 $\lceil 48/10 \rceil = 5$。总费用为 $48 \times 10 + 5 \times 100 = 980$，不超过预算 1000。

目标高度为 113 时，总土方量为 $4 \times 13 = 52$，发车次数为 $\lceil 52/10 \rceil = 6$。总费用为 $52 \times 10 + 6 \times 100 = 1120$，超过预算 1000。

因此最大可达高度为 112。