У вас есть несколько карт. На каждой карте написано целое число от \(1\) до \(n\): в частности, для каждого \(i\) от \(1\) до \(n\) у вас есть \(a_i\) карт, на которых написано число \(i\).
Также существует магазин, в котором продается неограниченное количество карт каждого типа. У вас есть \(k\) монет, поэтому вы можете купить в общей сложности не более \(k\) новых карт, и карты, которые вы покупаете, могут содержать любые целые числа от \(\mathbf{1}\) до \(\mathbf{n}\), включительно.
После покупки новых карт вы должны разбить все свои карты на колоды согласно следующим правилам:
- все колоды должны иметь одинаковый размер;
- нет пары карт с одинаковым числом в одной колоде.
Найдите максимально возможный размер колоды после покупки карт и их оптимального разбиения.
Примечание
В первом наборе входных данных вы можете купить одну карту с числом \(1\), и ваш набор карт станет таким: \([1, 1, 1, 1, 2, 2, 3, 3]\). Вы можете разбить их на колоды \([1, 2], [1, 2], [1, 3], [1, 3]\). Они все имеют размер \(2\), и все содержат разные значения. Можно показать, что невозможно получить разбиение с колодами размером больше \(2\), поэтому ответ — \(2\).
Во втором наборе входных данных вы можете купить две карты с числом \(1\) и одну карту с числом \(3\), и ваш набор карт станет таким: \([1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]\). Его можно разбить на колоды \([1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]\). Можно показать, что нельзя получить разбиение с колодами размером больше \(3\), поэтому ответ — \(3\).