题目描述

LK有$n$个容量无穷大的水杯，它们从$1\sim n$编号，初始时$i$号水杯中装有$A_i$单位的水。

你可以进行不超过$k$次操作，每次操作需要选择一个满足$1≤x≤n−1$的编号$x$，然后把$x$号水杯中的水全部倒入$x+1$号水杯中。

最后你可以任意选择恰好一个水杯，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

输入格式

第一行一个正整数$n$，表示水杯的个数。

第二行一个非负整数$k$，表示操作次数上限。

第三行$n$个非负整数，相邻两个数用空格隔开，表示水杯的初始装水量 $A_1\sim n$。

输出格式

一行，仅一个非负整数，表示答案。

样例

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

3813

数据规模与约定

• 对于$10\%$的数据，保证$n≤10$。
• 对于$30\%$的数据，保证$n≤100$。
• 对于$50\%$的数据，保证$n≤1000$。
• 对于$70\%$的数据，保证$n≤10^5$。
• 对于$100\%$的数据，保证 $1≤n≤10^6，0≤k≤n−1，0≤A_i≤1000$。