#P27. 教室

教室

题目描述

HGNUHGNU 小学中,有 nn 间有无穷多座位的教室,每个教室里有一定数量的学生。教小学信息技术的王老师想进行不超过 kk 次操作,每次操作选择一个数 mm,将第 mm 间教室中的学生都聚集到第 m+1m+1 间教室中。最后他将选择学生最多的教室,将教室里的学生都带到机房上机,请你求出他最多能带多少学生去机房上机。

输入格式

两行,第一行输入两个数 n(1n106)n(1 \le n \le 10^6)k(0kn1)k(0 \le k \le n-1),第二行输入长度为 nn 、以空格分隔的数组 class(0class[i]103)class(0 \le class[i] \le 10^3),表示每间教室的初始学生数量。

输出格式

一行,输出王老师最多能带多少学生去机房。

样例

10 5
890 965 256 419 296 987 45 676 976 742
3813