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