배열 덮기

미샤에게 길이가 $n$인 정수 배열이 있다. 미샤는 배열의 모든 원소가 선택한 부분 배열 중 적어도 하나에 포함되도록 서로 다른 연속 부분 배열을 $k$개 선택하려고 한다.

미샤는 각 부분 배열의 원소 합을 구하고 이 합들을 모두 더한다. 이때 얻을 수 있는 값이 최대가 되도록 부분 배열을 고른다.

첫 번째 줄에 두 정수 $n$과 $k$($1 \le n \le 100000$, $1 \le k \le \frac{n \cdot (n + 1)}{2}$)가 주어진다. 각각 배열의 원소 개수와 반드시 선택해야 하는 서로 다른 부분 배열의 개수이다.

두 번째 줄에는 배열의 원소인 정수 $n$개 $a_i$($-50000 \le a_i \le 50000$)가 주어진다.

서로 다른 부분 배열 $k$개를 골라 미샤가 얻을 수 있는 최댓값을 정수 하나로 출력한다.