Subarray Up To K

Problem Statement

Given an array $a$ of $n$ integers $a_1, a_2, ..., a_n$, as well as an integer $k$, determine the sum of the subarray which has a sum which is less than or equal to $k$. There will always be a subarray with a sum of $0$. If there is no subarray with sum less than or equal to $k$ then output $-1$.

Remember that a subarray is a selection of continuous elements of $a$.

Input Format

Your first line will contain two space-separated integers $n$ and $k$. Your next line will contain $n$ space-separated integers $a_1, ..., a_n$.

Output Format

You should output the largest subarray sum less than or equal to $k$. If there is no subarray with sum less than or equal to $k$ then output $-1$.

Constraints

• $1 \leq n \leq 10^5$
• $-10^9 \leq a_i \leq 10^9$
• $-10^9 \leq k \leq 10^9$

Sample Cases

6 13
100 -4 2 7 2 5

12

Explanation 2

The subarray with sum of $12$ is $[-4, 2, 7, 2, 5]$.

5 5
1 2 -4 2 5

5

Explanation 2

The subarray with sum of $5$ is $[5]$.