311293: CF1967A. Permutation Counting

A. Permutation Countingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have some cards. An integer between $1$ and $n$ is written on each card: specifically, for each $i$ from $1$ to $n$, you have $a_i$ cards which have the number $i$ written on them.

There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy $k$ new cards in total, and the cards you buy can contain any integer between $1$ and $n$.

After buying the new cards, you rearrange all your cards in a line. The score of a rearrangement is the number of (contiguous) subarrays of length $n$ which are a permutation of $[1, 2, \ldots, n]$. What's the maximum score you can get?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t\ (1\le t\le 100)$. The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1\le n \le 2 \cdot 10^5$, $0\le k \le 10^{12}$) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$) — the number of cards of type $i$ you have at the beginning.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a single line containing an integer: the maximum score you can get.

ExampleInput

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

Output

11
15
15
22
28
32
28
36

Note

In the first test case, the final (and only) array we can get is $[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$ (including $11$ single $1$s), which contains $11$ subarrays consisting of a permutation of $[1]$.

In the second test case, we can buy $0$ cards of type $1$ and $4$ cards of type $2$, and then we rearrange the cards as following: $[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]$. There are $8$ subarrays equal to $[1, 2]$ and $7$ subarrays equal to $[2, 1]$, which make a total of $15$ subarrays which are a permutation of $[1, 2]$. It can also be proved that this is the maximum score we can get.

In the third test case, one of the possible optimal rearrangements is $[3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]$.

题目大意：
题目是关于计算排列数量的。你有一些卡片，每张卡片上写着一个介于1和n之间的整数。具体来说，对于每个i从1到n，你有\(a_i\)张写有数字i的卡片。还有一个商店，里面有每种类型的无限张卡片。你有k个硬币，所以总共可以购买k张新卡片，而且你购买的卡片可以包含1到n之间的任何整数。

购买新卡片后，你将所有卡片重新排列成一行。一个重新排列的得分是由长度为n的连续子数组，它们是[1, 2, ..., n]的排列的数量。求你能得到的最大分数是多少。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数n，k（1≤n≤2×10^5，0≤k≤10^12），表示不同类型卡片的数量和硬币的数量。
- 第二行包含n个整数\(a_1, a_2, ..., a_n\)（1≤\(a_i\)≤10^12），表示你最初拥有的类型i的卡片数量。
- 保证所有测试用例的n之和不超过5×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
```

注意：
- 在第一个测试用例中，我们能得到的最终（也是唯一的）数组是[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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]。题目大意： 题目是关于计算排列数量的。你有一些卡片，每张卡片上写着一个介于1和n之间的整数。具体来说，对于每个i从1到n，你有\(a_i\)张写有数字i的卡片。还有一个商店，里面有每种类型的无限张卡片。你有k个硬币，所以总共可以购买k张新卡片，而且你购买的卡片可以包含1到n之间的任何整数。 购买新卡片后，你将所有卡片重新排列成一行。一个重新排列的得分是由长度为n的连续子数组，它们是[1, 2, ..., n]的排列的数量。求你能得到的最大分数是多少。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数n，k（1≤n≤2×10^5，0≤k≤10^12），表示不同类型卡片的数量和硬币的数量。 - 第二行包含n个整数\(a_1, a_2, ..., a_n\)（1≤\(a_i\)≤10^12），表示你最初拥有的类型i的卡片数量。 - 保证所有测试用例的n之和不超过5×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 ``` 注意： - 在第一个测试用例中，我们能得到的最终（也是唯一的）数组是[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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]。