B. Step Gambling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sensible gambling is crucial to ensure that the activity remains enjoyable and does not spiral into harmful behavior. It involves setting limits on time and money spent, understanding the risks, and knowing when to walk away. By practicing self-control and being aware of the potential consequences, individuals can avoid the dangers of addiction and financial strain. Responsible gambling encourages balance, helping players enjoy the experience without it negatively impacting their lives or well-being.

You have $$$k$$$ amount of money which u are ready to risk for gambling and your goal is to have the most amount of money in the end

You are given an array of n integers which determine the money gained or lost playing the ith game.

Here's the description of the game, you can start playing from any index you want. Note that you can back out at any time

If you are currently playing game $$$i$$$, and this is your $$$j$$$'th game so far; Then the next game that you will be playing is game $$$i + j$$$

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of testcases

  • The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 2*10^5$$$) — the size of the array and $$$k$$$ ($$$1 \leq k \leq 10^9$$$) — the initial money you hold
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the game.
It is guaranteed that the sum of all $$$n$$$ across all test cases does not exceed $$$2 * 10^5$$$.
Output

For each test, print the maximum amount of money u can hold after playing the most desirable situation

Example
Input
3
5 5
-1 -1 -1 -1 -1
4 1
100 -500 -200 100
4 3
1 2 3 4
Output
5
101
10