3.4 Ryn Blackwood’s Adventure: Hallway of Gold
The Chamber’s stone door swings open, and Ryn Blackwood steps forward into a glittering expanse: the Hallway of Gold. This endless corridor stretches like a great line carved into time itself, marked by coordinates as though upon an invisible axis.
Ryn begins at the very center — the 0th coordinate. Along this axis, there are coordinates that shimmer faintly, some of them holding ‘c’ coins. An array is given, telling her which coordinates the coins are located.
But the Hallway tests not only her courage but her swiftness. The enchantment of the place is cruel:
> Each time Ryn takes a single step one second passes.
> With every passing second, the Hallway consumes one coin from all the coordinates.
> Thus, when Ryn reaches a coordinate, she can only collect coins that have not yet vanished by then.
She may initially choose the direction to travel in, moving left or right, but has to continue down that path.
What is the maximum number of coins Ryn can gather before time steals them away?
Constraints
1<=n<=10^5
1<=c<=10^2
-10^3≤ai<10^3
Input Format
The first line contains an integer t — the number of test cases
Each test case contains two lines:
First line has integer n and c signifying number of coordinates in the array and the number of coins at each coordinate
Second line has n space separated integer signifying the coordinates where c coins are kept
Output Format
Maximum number of coins that can be gathered
Example 1
Input:
2
5 8
-3 -1 2 4 5
3 10
1 2 3
Output:
13
24
Explanation:
In case 1, Ryn can choose to go right. At 2nd coordinate she will earn 6 coins followed by 4 coins at 4th coordinate and 3 coins at 5th.
6+4+3=13
In case 2, there is only one direction. Ryn will earn 24 coins.
Log In to solve the Question