你有一些牌。每张卡片上都写有 $$$1$$$ 和 $$$n$$$ 之间的整数:具体而言,对于从 $$$1$$$ 到 $$$n$$$ 的每张 $$$i$$$,您都有 $$$a_i$$$ 卡片,上面写有数字 $$$i$$$。
还有一家商店,其中包含各种类型的无限卡。您拥有 $$$k$$$ 硬币,因此您总共可以购买 $$$k$$$ 张新卡,并且您购买的卡可以包含 $$$1$$$ 到 $$$n$$$ 之间的任何整数。
购买新卡后,您将所有卡重新排列成一行。重新排列的分数是长度为 $$$n$$$ 的(连续)子数组的数量,它们是 $$$[1, 2, \ldots, n]$$$ 的排列。你能得到的最高分数是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量$$$t\ (1\le t\le 100)$$$。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1\le n \le 2 \cdot 10^5$$$, $$$0\le k \le 10^{12}$$$) - 不同类型卡片的数量和硬币的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) - 您一开始拥有的 $$$i$$$ 类型的卡片数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含一个整数:您可以获得的最高分数。
示例
输入 #1
8 1 10 1 2 4 8 4 3 4 6 1 8 3 9 7 6 2 5 3 6 6 7 4 6 9 7 7 6 1 7 6 2 4 3 3 10 10 1 3 1 2 1 9 3 5 7 5 9 8 5 8 7 5 1 3 2 9 8
输出 #1
11 15 15 22 28 32 28 36
注意
在第一个测试用例中,我们可以获得的最终(也是唯一)数组是 $$$[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$$$ (包括 $$$11$$$ 单个 $$$1$$$s),其中包含 $$$11$$$ 子数组,这些子数组由以下排列组成$$$[1]$$$。
在第二个测试用例中,我们可以购买 $$$0$$$ 类型为 $$$1$$$ 的卡片和 $$$4$$$ 类型为 $$$2$$$ 的卡片,然后我们将卡片重新排列如下: $$$[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]$$$。有 $$$8$$$ 子数组等于 $$$[1, 2]$$$ 和 $$$7$$$ 子数组等于 $$$[2, 1]$$$,总共有 $$$15$$$ 子数组,它们是 $$$[1, 2]$$$ 的排列。也可以证明这是我们能得到的最高分。
在第三个测试用例中,可能的最佳重新排列之一是 $$$[3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]$$$。