题目描述

有 $n$ 个容量无限的水壶，编号从 $1$ 到 $n$。初始时第 $i$ 个水壶中有 $A_i$ 单位的水。

你可以执行最多 $k$ 次操作，每次操作选择一个编号 $x$（$1 \le x \le n-1$），将第 $x$ 个水壶中的水全部倒入第 $x+1$ 个水壶中。

操作完成后，你可以选择恰好一个水壶喝掉里面的全部水。求你最多能喝到多少单位的水。

输入格式

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

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

第三行 $n$ 个非负整数，用空格隔开，依次表示 $A_1, A_2, \cdots, A_n$。

输出格式

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

样例

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

3813

提示

数据规模与约定

• 对于 $10\%$ 的数据，$n \le 10$；
• 对于 $30\%$ 的数据，$n \le 100$；
• 对于 $50\%$ 的数据，$n \le 10^3$；
• 对于 $70\%$ 的数据，$n \le 10^5$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le k \le n-1$，$0 \le A_i \le 10^3$。