E. Заполни матрицу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана квадратная матрица, состоящая из $$$n$$$ строк и $$$n$$$ столбцов ячеек, оба пронумерованы от $$$1$$$ до $$$n$$$. Ячейки раскрашены в белый или черный цвет. Ячейки с $$$1$$$ до $$$a_i$$$ черные, а ячейки с $$$a_i+1$$$ до $$$n$$$ белые, в $$$i$$$-м столбце.

Вы хотите разместить $$$m$$$ целых чисел в матрице, от $$$1$$$ до $$$m$$$. Есть два правила:

  • в каждой клетке должно быть не больше одного числа;
  • в черных клетках не должно быть чисел.

Красота матрицы — это количество таких $$$j$$$, что $$$j+1$$$ написано в той же строке, в следующем столбце от $$$j$$$ (в соседней справа ячейке).

Чему равна максимальная красота матрицы?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер матрицы.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — количество черных клеток в каждом столбце.

В третьей строке записано одно целое число $$$m$$$ ($$$0 \le m \le \sum \limits_{i=1}^n n - a_i$$$) — количество чисел, которые требуется разместить в матрице. Обратите внимание, что это число может не поместиться в 32-битный целый тип данных.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — максимальную красоту матрицы после того, как вы разместите в ней все $$$m$$$ целых чисел. Обратите внимание, что дается не больше чисел, чем белых клеток в матрице, так что ответ всегда существует.

Пример
Входные данные
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