← 返回题目列表

Codeforces · 1841/E

E. 填充矩阵

中文机器翻译题面 查看原题

有一个方阵,由 $$$n$$$ 行和 $$$n$$$ 列单元格组成,编号从 $$$1$$$ 到 $$$n$$$。细胞颜色为白色或黑色。在第 $$$i$$$ 列中,从 $$$1$$$ 到 $$$a_i$$$ 的单元格为黑色,从 $$$a_i+1$$$ 到 $$$n$$$ 的单元格为白色。

您想要在矩阵中放置 $$$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$$$ 整数后,矩阵的最大美感。请注意,整数的数量不会多于白色单元格的数量,因此答案始终存在。

示例

输入 #1

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

输出 #1

6
3
4
4
16
0