Permutation Counting
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 1400
Tags: binary search, greedy, implementation, math, sortings

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 format:
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 format:
For each test case, output a single line containing an integer: the maximum score you can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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]$$$.

Example input:
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

Example output:
11
15
15
22
28
32
28
36

Editorial:
If $$$a_1=a_2=\cdots=a_n$$$ and $$$k=0$$$, it's obvious that the optimal rearrangement is $$$[1,2,\cdots,n,1,2,\cdots,n,\cdots,1,2,\cdots,n]$$$, because every subarray of length $$$n$$$ is a permutation of $$$1\sim n$$$.
WLOG, assume that $$$a_1\ge a_2\ge\cdots a_n=w$$$. If $$$k=0$$$, we can insert more numbers at the back and form more permutations. But because $$$a_n$$$ is the minimum number, we can only make these subarrays become permutations:

The remaining cards can be placed arbitrarily. This won't always be satisfied (if $$$a_{n-1}=w$$$, the green subarray won't exist). But this will only happen if $$$a_{n-1}=w$$$ is also minimum. It's the same for $$$a_{n-2}$$$ etc. So we can calculate the answer:
$$$$$$ans = nw - \sum_{i=1}^n [a_i = w] + 1$$$$$$
Considering $$$k > 0$$$ cases, we find that every time we choose a minimum $$$a_i$$$ and increase it by $$$1$$$, the answer will be increased. And the answer won't change if we increase some other $$$a_i$$$. So we have two different approaches:
• Sort the array $$$a$$$, enumerate the range where the minimum number will be, and check if it's possible. If so, we can just calculate by using the above equation.
• Binary search the $$$w$$$ after buying cards. After calculating the array $$$a$$$ after buying cards, we will be able to calculate the answer.
Time complexity: $$$\mathcal O(n\log n)$$$ or $$$\mathcal O(n\log a_i)$$$.