Water Problem
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

Mr.Z lives in two-dimensional world where there is a pool.

The pool is constructed by N walls, the width of each wall is one unit and the height of i-th wall is Hi unit.

As Fig.1, the black area is wall and the heights of them are {0,1,0,2,1,0,1,3,2,1,2,1}. The blue area is water. In this case, we can know that the volume of water is 6 units.

Now, Mr.Z wants to add the height of some walls to make the pool hold more water. But for some reason, Mr.Z can add no more than K units of wall.

Mr. Z wants to find an optimal solution that will maximize the volume of water the expanded pool could hold.

Can you help Mr.Z ?

Fig.1 The initial status of walls. The volume of water is 6 units.

Fig.2 One solution of added 2 units of wall. The volume of water is 12 units.

Fig.3 Another solution of added 2 units of wall. The volume of water is 11 units.

As you can see, solution in Fig.2 is better than in Fig.3.

输入描述:

The first line contains an integer T which means there are T test cases (T <= 20).
For each test case, there are three lines：
The first line contains an integer N(1<=N<=400).
The second line contains N integers H1 H2 ... Hn (0 <= H1,H2,……,Hn <= 107) separated by space, representing the height of N walls in order.
The third line contains a single number K. (K <= 107)

输出描述:

For each test case, please output a single number in a line indicating the maximum unit of water the expanded pool could hold.
示例1

输入

复制 
1
12
0 1 0 2 1 0 1 3 2 1 2 1
2

输出

复制 
12