你有一些卡牌。每张卡牌上都写着一个介于 $1$ 和 $n$ 之间的整数：具体来说，对于每个 $i$（从 $1$ 到 $n$），你拥有 $a_i$ 张写有数字 $i$ 的卡牌。

此外还有一家商店，里面有无限张每种类型的卡牌。你拥有 $k$ 枚硬币，因此你总共可以购买 $k$ 张新卡牌，购买的卡牌可以包含 $1$ 到 $n$ 之间的任意整数。

购买新卡牌后，你将所有卡牌排成一排。一种排列方式的得分是其中长度为 $n$ 且是 $[1, 2, \dots, 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, \dots, 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），它包含 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]$。