#957. [NOI Online #3 提高组] 水壶

[NOI Online #3 提高组] 水壶

[NOI Online #3 提高组] 水壶

题目描述

nn 个容量无穷大的水壶,它们从 1n1\sim n 编号,初始时 ii 号水壶中装有 AiA_i 单位的水。

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

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

输入格式

第一行一个正整数 nn,表示水壶的个数。

第二行一个非负整数 kk,表示操作次数上限。

第三行 nn 个非负整数,相邻两个数用空格隔开,表示水壶的初始装水量 A1A_1, A2A_2, \cdots, AnA_n

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3813

提示

数据规模与约定

  • 对于 10%10\% 的数据,保证 n10n \leq 10
  • 对于 30%30\% 的数据,保证 n100n \leq 100
  • 对于 50%50\% 的数据,保证 n103n \leq 10^3
  • 对于 70%70\% 的数据,保证 n105n \leq 10^5
  • 对于 100%100\% 的数据,保证 1n1061\leq n\leq 10^60kn10\leq k \leq n-10Ai1030\le A_i\le 10^3