Problem : Aesthetic Building Modification

Launch Code Editor

There are N consecutive buildings in a society. The owners decided to increase the heights of the buildings. Being aesthetically

oriented, they wanted to ensure that the heights (all measured as number of floors in the building) of consecutive buildings differ

at most by one floor so that the skyline of the buildings look pleasing. It is also desired that after the increase of heights, the

profile of the entire society will look like an inverted "V" - that is the heights will increase up to the middle building and thereafter

the height will decrease steadily. In other words, for p < N/2, the heights of the buildings after modification will satisfy the

condition H p+1 - H p = 1 and for p > N/2, the heights will satisfy H p - H p+1 = 1.

Notifications

Status messages

The cost of increase is computed as follows. Let f be the function defined by f(x) = 1000 max(x,1) 2 . That is f(10) = 100000 while

f(-10) = 1000.

To increase the height by h > 0 floors, the total cost is

f(B) + f(B-1) + f(B-2) + .... + f(B-(h-1))

where B is a given base cost.

We cannot decrease the height of any building. If the number of buildings is even, there will be two buildings at the middle point

with the same height and their height will be the highest.

Input Format:

First line containing an integer T, the number of test cases.

In the next T pairs of lines each pair containing an integer N and a base price B.

A second line containing space separated N integers containing heights of the N buildings in order.

Output Format:

T lines where ith line contains the minimum cost required for the ith test case.

Constraints:

1 ≤ N ≤ 10 3

1 ≤ H i ≤250

1 ≤ B ≤ 10 3

Example 1

Input

1

6 5

2 6 11 5 3 1

Output

282000

Explanation

Initially, the height of 6 buildings are [2 6 11 5 3 1]

For the first n/2 elements, criteria is: Hp+1 - Hp=1

Consider the height of first 3 buildings [2 6 11], so it becomes [9 10 11]

So the height of the next building should be 11. Also the heights of the last n/2 buildings should be [11 10 9] and thus the final

heights of the buildings are [9 10 11 11 10 9]

For building 1,

Increase in height is 7 and the cost is

f(5) + f(4) + f(3) + f(2) + f(1) + f(0) + f(-1)=1000(5 2 +4 2 +3 2 +2 2 +1 2 +1 2 +1 2 =25+16+9+4+1+1+1)=57000 rupees

In the same way,

For building 2, cost=54000 rupees

For building 3, cost= 0 rupees

For building 4, cost= 56000 rupees

For building 5, cost= 57000 rupees

For building 6, cost= 58000 rupees

Total cost required 282000 rupees