题目描述

在一座城市中，划分为多个区域，每个区域内建设一个充电站，充电站内设有多个充电桩，充电站之间需要保持合理的距离。定义：

• n：区域充电站的数目。
• station[i]：表示第 i 个充电站中充电桩的数量。
• r：充电站可覆盖的相邻区域范围，满足条件 |i-j| <= r。
• k：需要新增的充电桩数量。

题目内容

随着新能源汽车的蓬勃发展，新能源汽车充电桩的覆盖密度越来越重要。某汽车公司建设充电桩的思路如下:

一条高速沿线，每个区域建设一个充电站，充电站内有多个充电桩，充电站之间保持合理的距离，每个充电站可以覆盖相邻范围的多个区域

我们使用$n$来表示区域充电站的数目，使用$station[i]$数组表示第i个充电站中充电桩的数目。

给定一个范围$r$，$i$区域可以被附近范围内的充电站覆盖，$|i-j|<=r,0<=i,j<=n-1,|i-j|$表示绝对值。

因此覆盖区域的充电桩包括$i$区域内充电站的充电桩以及满足上述覆盖条件区域$j$区域充电站的充电桩。

汽车公司打算在一些城市新增$k$个充电桩，如何分配这$k$个充电桩给充电站，使得所有区域总，被充电桩覆盖最少区域的充电桩数目最大化。

输入描述

第一行输入为$n$，表示有$n$个充电站区域，取值范围$[0,100000]$

第二行输入$为station[n]$数组，表示n个充电站中充电桩的数目$[0,100000]$

第三行输入为$r$，表示充电站可覆盖的相邻区域的范围$[0,n-1]$

第四行输入为$k$，表示需要新增的充电桩数目$[0,1000000000]$

输出描述

输出被充电桩覆盖最少的区域的充电桩的数目

样例1

输入

5
1 2 4 5 0
1 
2

输出

5

说明

最优方案是把$2$个充电桩都放在充电站$1$，这样每个充电站的充电桩数目分别为$1\ 4\ 4\ 5\ 0$。

• 区域$0$的覆盖充电桩为$1+4=5$,
• 区域$1$为$1+4+4=9$，
• 区域$2$为$4+4+5=13$，
• 区域$3$为$5+4=9$，
• 区域$4$为$5+0=5$

充电桩覆盖数目最少是$5$

无法得到更优解，所以我们返回$5$。

样例2

输入

4
4 4 4 4
0
2

输出

4

说明

无论怎么分配新增的$3$个充电站，总有一个区域的充电桩覆盖数目是$4$