问题描述

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

你可以进行不超过k次操作，每次操作需要选择一个满足1≤x≤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

样例解释

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

数据范围

• 对于10%的数据，保证n≤10。
• 对于30%的数据，保证n≤100。
• 对于50%的数据，保证n≤10³。
• 对于70%的数据，保证n≤10⁵。
• 对于100%的数据，保证1≤n≤10⁶，0≤k≤n-1，0≤A_i≤10³。