CF1967A Permutation Counting

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?

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

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

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