K-th Smallest Subarray Sum

Given an integer array and a positive integer \(k\), your task is to find the \(k\)-th smallest sum among all possible contiguous subarrays of the array. A contiguous subarray is defined as a sequence of consecutive elements from the array.

Formally, for an array \(a\) with \(n\) elements, consider all sums of the form \[ S(i,j)=\sum_{t=i}^{j}a_t, \quad 1 \le i \le j \le n, \] and output the \(k\)-th smallest value in the sorted order of these sums. It is guaranteed that \(1 \le k \le \frac{n(n+1)}{2}\).

inputFormat

The input is read from standard input (stdin) and consists of two lines.

The first line contains two space-separated integers \(n\) and \(k\), where \(n\) is the number of elements in the array, and \(k\) indicates that you need to find the \(k\)-th smallest contiguous subarray sum.

The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output the \(k\)-th smallest contiguous subarray sum to standard output (stdout).

5 3
1 2 -1 3 4

1