求助

敌人们正计划入侵x的城堡，x需要你来制定守卫策略。城堡三面环山，只需要守卫城堡一面的城墙。城墙划分为 n 段，第 i 段已经部署了 a[i]​名弓箭手。所有弓箭手的射程都是 r，意味着位于第 ii 段的弓箭手可以射击到正在攻击第 j 段城墙的敌人，其中 j 满足 ∣i−j∣≤r。

第 i 段城墙的防御值定义为所有能够射击到正在攻击第 i 段城墙敌人的弓箭手总和。整体防御值定义为所有 n 段城墙防御值的最小值。

现在还有 k 名弓箭手尚未部署，你可以将任意数量的弓箭手部署在任意位置。x想希望你成最大化整体防御值。

输入格式

第一行输入三个整数 n, r, k分别表示城墙段数，弓箭手射程，以及未部署的弓箭手数量。

第二行输入 n 个整数 a[1], a[2], a[3], ……a [n]

a[i]表示第 i 段初始的弓箭手数量。

输出格式 输出一个整数，表示最优部署下的防御值。

数据范围

对于 20% 的数据，满足 , k = 0n≤10 ^ 3 ,k=0 。

另有 10% 的数据满足 n≤10 ^ 3 。

另有 10% 的数据满足k=0。

对于 100% 的数据1≤n≤10 ^ 5 ,0≤r≤n,0≤k≤10 ^ 18 ,0≤a[ i]​≤10 ^ 9 。

样例输入1

5 0 6

5 4 3 4 9

样例输出1

5

样例输入2

4 2 0

1 2 3 4

样例输出2

6

样例输入3

5 1 1

2 1 2 1 2

样例输出3

3