← 返回题目列表

Codeforces · 720/F

F. 数组覆盖

中文机器翻译题面 查看原题

Misha 有一个长度为 n 的整数数组。他想要选择k个不同的连续子数组,使得数组的每个元素至少属于所选择的子数组之一。

Misha 希望以这样的方式选择子数组:如果他计算每个子数组的元素总和,然后将所有这些总和相加,则结果值是最大可能的。

输入

输入的第一行包含两个整数:n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) - 数组中元素的数量以及必须选择的不同子数组的数量。

第二行包含 n 个整数 ai ( - 50 000 ≤ ai ≤ 50 000) — 数组的元素。

输出

输出一个整数——Misha 通过选择 k 个不同的子数组可以获得的最大可能值。

示例

输入 #1

5 4
6 -4 -10 -4 7

输出 #1

11