题目内容

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

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

我们使用 $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]$

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

输入

输出

说明

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

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

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

输入

输出

说明

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