A. 置换计数

时间限制：每个测试用例 $2$ 秒 内存限制：$256$ 兆字节

题目描述

你有一些卡片。每张卡片上写着一个 $1$ 到 $n$ 之间的整数： 具体来说，对于每个从 $1$ 到 $n$ 的 $i$，你拥有 $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 \times 10^5$，$0 \le k \le 10^{12}$）。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^{12}$）。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数：可获得的最大得分。

样例输入

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

样例输出

11
15
15
22
28
32
28
36

样例解释

第一个测试用例：最终只能得到 $11$ 个连续的 $1$，包含 $11$ 个符合要求的长度为 $1$ 的排列子数组，得分为 $11$。

第二个测试用例：购买 $0$ 张数字 $1$、$4$ 张数字 $2$，排列为 $1,2,1,2,\dots$，共有 $8$ 个 $[1,2]$ 和 $7$ 个 $[2,1]$，总得分 $15$。