write a go solution for A. Cards Partitiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDJ Genki vs Gram - Einherjar Joker⠀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 at most k new cards in total, and the cards you buy can contain any integer between mathbf1 and mathbfn, inclusive.After buying the new cards, you must partition all your cards into decks, according to the following rules:   all the decks must have the same size;  there are no pairs of cards with the same value in the same deck. Find the maximum possible size of a deck after buying cards and partitioning them optimally.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows.The first line of each test case contains two integers n, k (1<=n<=2*10^5, 0<=qk<=q10^16) — 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 (0<=a_i<=10^10, suma_i>=1) — the number of cards of type i you have at the beginning, for each 1<=qi<=qn.It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.OutputFor each test case, output a single integer: the maximum possible size of a deck if you operate optimally.ExampleInput93 13 2 25 42 6 1 2 42 1001410065408 1000000000010 87 4 6 6 9 3 10 2 8 72 122 22 700 11 013 02 1 23 10 3 3Output2
3
1
7
2
2
1
1
2
NoteIn the first test case, you can buy one card with the number 1, and your cards become [1,1,1,1,2,2,3,3]. You can partition them into the decks [1,2],[1,2],[1,3],[1,3]: they all have size 2, and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than 2, so the answer is 2.In the second test case, you can buy two cards with the number 1 and one card with the number 3, and your cards become [1,1,1,1,2,2,2,2,2,2,3,3,4,4,5,5,5,5], which can be partitioned into [1,2,3],[1,2,4],[1,2,5],[1,2,5],[2,3,5],[2,4,5]. You can show that you cannot get a partition with decks of size greater than 3, so the answer is 3.. Output only the code with no comments, explanation, or additional text.