题目描述Description

我的名字叫做埃德加，是戴夫最好的朋友之一，他的理想是成为一名植物学家，而我，则想成为一名伟大的发明家，十年前，我们一起参加了一个军方对空间裂缝的研究，（戴夫负责研究异界植物，我负责维护裂缝的稳定）前去裂缝中探险的人们带来了很多有趣的生物与植物，我也有幸进入过裂缝一次，那里的风景非常美丽并且似乎没有智慧生物的样子，一切都是那么的美好，但是……突如其来的意外很快就证明我们错了……无数奇形怪状的植物从裂缝中涌出，它们强大的生命力使他们几乎不会被人类人热武器杀死……人类很快就溃败了，而这些恶魔植物居然还会通过吸食人类的大脑来获得知识，人类在三年内慢慢的灭绝了……只有少部分对植物有益的人类还活着戴夫也在其中，而我，被植物们虐待致死。

​ 在死后那无尽的黑暗中，我似乎又看到了光明……我挣扎着想要起身，最后我爬了起来，而我身处于一个巨大的尸体堆放处，我摸了摸自己的身体，它早已失去了温度，呵，我变成僵尸了吗，我在心里这么想着，不过戴夫还活着呢……我要去救他，我看向远方，无数的尸体中一个个人影站立了起来，一个伟大的计划在我心里产生，我，用了一年的时间建立了我的巨型钢铁机器人和我的僵尸王国，现在，戴夫，我来救你了……

​ 僵尸…全都是僵尸…戴夫独自喃喃道，他来到了禅境花园中。他发现只有在禅境花园中他才能获得一丝平静，所以戴夫愈加珍惜呆在禅境花园的时间。并且想保护这些植物。

​ 然而好景不长，很快僵尸大军就攻破了戴夫的后院。来到了戴夫最后珍视的地方，禅境花园。为了防御来犯的僵尸。他改变了植物的布局，把所有植物都排成一列连续的植物。每个植物都有一个初始防御力。并且为了防守来犯的僵尸，他拿出了珍藏已久的水壶。水壶的水还足够用m次，每次它可以选择连续的w个元素值增加1.戴夫想保护所有禅境花园的植物。所以今天他要把积累的水全部用出去，它的目标是让植物们都有更高的防御。然而僵尸们学会了群体攻击。如果攻击力大于防御力，植物就会死亡。每次会对所有植物一起造成攻击。而任何一个植物的死亡都会让戴夫陷入疯狂。所以整个花园的防御力等于花园中的防御力最小的植物的防御力。他想知道，经过它的努力，花园最大能达到的防御力是多少。

​ 换言之，他现在有n个排在一排的植物，每个植物有一个初始防御力ai。他可以让 一个连续的长度为w的区间内的所有植物防御力+1。由于防御力最低的植物决定了整体的防御力，他要让你帮忙求出整体防御力最大可以达到多少

输入格式Input

单组测试数据

第一行输入包含3个整数n,m,w.（1\leq w\leq n\leq 100000；1\leq m\leq 100000)

第二行包含n个整数，a_1,a_2,a_3......a_n(1\leq a_i\leq 1e9)表示n个植物的初始防御力

输出格式Output

输出一个整数，表示花园整体最大的防御力。

样例Sample

提示Hint

样例表示开始有6个植物，防御分别是{2，2，2，2，1，1}我们可以使用2次水壶，让一个长度为3的区间植物防御力全部+1。我们可以先选择后三个植物同时+1.所有植物的防御力变为{2，2，2，3，2，2}.第二次，我们可以让任意3个连续的植物防御力全部+1，不管选哪三个植物，总会有植物的防御力仍然等于2。所以整个花园能达到的最大整体防御力的值为2。

出题Author

徒手拆机甲

来源Source