#BT03. 整数均分线

整数均分线

整数均分线

一段录音被划成 nn 个片段,第 ii 个片段的评分为整数 aia_i,评分可以为负数。

你要保留一段长度至少为 LL 的非空连续片段。这段片段的得分为其平均评分向下取整后的整数。

请求出你能得到的最大得分。向下取整指不超过原数的最大整数,例如 ⌊−3.5⌋=−4\lfloor-3.5\rfloor=-4。

输入格式

第一行包含两个整数 n,Ln,L。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一个整数,表示最大得分。

样例 1

5 2
1 4 2 6 3
4

保留最后两个片段,其平均评分为 4.54.5,得分为 44。不存在得分大于 44 的合法片段。

样例 2

2 2
-5 -2
-4

数据范围

  • 1≤L≤n≤200 0001\le L\le n\le200\,000。
  • −106≤ai≤106-10^6\le a_i\le10^6。
  • 每个输入文件只有一组数据。