题目描述

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

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

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

输入格式

1. 第一行一个正整数 $n$，表示水杯的个数；
2. 第二行一个非负整数 $k$，表示操作次数上限；
3. 第三行 $n$ 个非负整数，相邻两个数用空格隔开，表示水杯的初始装水量 $A_1, A_2, \dots, A_n$。

输出格式

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

输入输出样例

输入样例

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

输出样例

3813

说明/提示

样例解释

样例中 $n=10$，$k=5$，初始装水量序列为 $[890, 965, 256, 419, 296, 987, 45, 676, 976, 742]$。 要使喝到的水量最多，需选择连续的若干个水杯合并，且合并所需操作次数不超过 $k$。合并 $m$ 个连续水杯（从 $i$ 到 $j$，$j \ge i$）需要的操作次数为 $j-i$ 次（每次将前一个水杯的水倒入后一个，共需 $j-i$ 步）。 当选择合并 $1 \sim 6$ 号水杯时，所需操作次数为 $6-1=5$ 次（刚好等于 $k$ 的上限），合并后的总水量为 $890+965+256+419+296+987=3813$。 经检查，其他任何合并方案的总水量均不超过 $3813$，因此答案为 $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$。