CF720F.Array Covering

Misha has an array of integers of length n. He wants to choose k different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.

Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible.

米沙有一个长度为 $n$ 的整数数组。他希望从中选出 $k$ 个互不相同的连续子数组，使得数组中的每个元素至少属于其中一个被选中的子数组。

米沙希望以这样的方式选择子数组：若先分别计算每个子数组中所有元素的和，再将这些和相加，则最终得到的总和尽可能大。

The first line of input contains two integers: n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen.

The second line contains n integers a__i ( - 50 000 ≤ a__i ≤ 50 000) — the elements of the array.

输入的第一行包含两个整数：$n$、$k$（$1 ≤ n ≤ 100\,000$，$1 ≤ k ≤ n·(n + 1) / 2$）—— 分别表示数组的元素个数以及必须选出的不同子数组的个数。

第二行包含 $n$ 个整数 $a_i$（$-50\,000 ≤ a_i ≤ 50\,000$）—— 表示数组的元素。

Output one integer — the maximum possible value Misha can get by choosing k different subarrays.

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