Array Covering

배열의 모든 원소를 덮도록 서로 다른 k개의 연속 부분 배열을 골라, 부분 배열 합의 총합이 최대가 되게 한다.

어려움8그리디정렬누적 합아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제1

문제

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.

입력

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 ai ( -50 000 ≤ ai ≤ 50 000) — the elements of the array.

출력

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