题目描述

有n个容量无穷大的水壶，它们从1~n编号，初始时i号水壶中装有Ai单位的水。 你可以进行不超过k次操作，每次操作需要选择一个满足1≤x≤n-1的编号x,然后把x号水壶中的水全部倒入x+1号水壶中。 最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

输入格式

第一行一个正整数n,表示水壶的个数。 第二行一个非负整数k,表示操作次数上限。 第三行n个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量A1,A2,...An.

输出格式

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

输入输出样例

输入#1

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

输出#1

3813

说明/提示

数据规模与约定

·对于10%的数据，保证$n≤10$。 ·对于30%的数据，保证$n≤100$。 ·对于50%的数据，保证$n≤10^3$。 ·对于70%的数据，保证$n≤10^5$。 ·对于100%的数据，保证$1≤n≤10^6,0≤k≤n-1,0≤Ai≤10^3$。