水壶(民间数据)

【题目描述】

有$n$个容量无穷大的水壶，它们从$1$到$n$编号,初始时i号水壶中装有$A_i$单位的水

你可以进行不超过$k$次操作，每次操作需要选择$1\leq x \leq n−1$的编号$x$,然后把$x$号水壶中的水全部倒入$x+1$号水壶中。

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

【输入格式】

第一行一个正整数$n$，表示水壶的个数;

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

第三行$n$个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量$A_1 , A_2 , .... A_n$;

【输出格式】

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

【样例输入】

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

【样例输出】

3813

【数据规模与约定】

·对于10%的数据，保证$n \leq 10^1$;

·对于30%的数据，保证$n \leq 10^2$;

·对于50%的数据，保证$n \leq 10^3$;

·对于70%的数据，保证$n \leq 10^5$;

·对于100%的数据，保证$1 \leq n \leq 10^6 , 0 \leq k \leq n-1 , 0 \leq A_i \leq 10^3$;