You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the matrix.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) — the number of black cells in each column.

The third line contains a single integer $m$ ($0 \le m \le \sum \limits_{i=1}^n n - a_i$) — the number of integers you have to write in the matrix. Note that this number might not fit into a 32-bit integer data type.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

Output

For each testcase, print a single integer — the maximum beauty of the matrix after you write all $m$ integers in it. Note that there are no more integers than the white cells, so the answer always exists.

6
3
0 0 0
9
4
2 0 3 1
5
4
2 0 3 1
6
4
2 0 3 1
10
10
0 2 2 1 5 10 3 4 1 1
20
1
1
0
 
 
 
 
 
 
 
 
 

6
3
4
4
16
0