[Solution] The Enchanted Forest Codeforces Solution | Codeforces Problem Solution 2022

[Solution] The Enchanted Forest Codeforces Solution | Codeforces Problem Solution 2022

D. The Enchanted Forest

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Marisa comes to pick mushrooms in the Enchanted Forest.

The Enchanted forest can be represented by n$n$ points on the X$X$-axis numbered 1$1$ through n$n$. Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by a1,a2,…,an$a_1,a_2,\dots ,a_n$.

Marisa can start out at any point in the forest on minute 0$0$. Each minute, the followings happen in order:

• She moves from point x$x$ to y$y$ (|x−y|≤1$|x-y|\le 1$, possibly y=x$y=x$).
• She collects all mushrooms on point y$y$.
• A new mushroom appears on each point in the forest.

Solution Click Below:-  CLICK HERE

Note that she cannot collect mushrooms on minute 0$0$.

Now, Marisa wants to know the maximum number of mushrooms she can pick after k$k$ minutes.

Input

Each test contains multiple test cases. The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. The description of the test cases follows.

Cirno's Perfect Bitmasks Classroom Codeforces Solution

Patchouli's Magical Talisman Codeforces Solution

Manipulating History Codeforces Solution

The Enchanted Forest Codeforces Solution

Railway System Codeforces Solution

Sanae and Giant Robot Codeforces Solution

The first line of each test case contains two integers n$n$, k$k$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤k≤109$1\le k\le {10}^9$) — the number of positions with mushrooms and the time Marisa has, respectively.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) — the initial number of mushrooms on point 1,2,…,n$1,2,\dots ,n$.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print the maximum number of mushrooms Marisa can pick after k$k$ minutes.