B. Продавец Карел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карел работает продавцом в автосалоне. В автосалоне имеется $$$n$$$ различных моделей автомобилей. В наличии есть $$$a_i$$$ автомобилей $$$i$$$-й модели. Карел — отличный продавец и может убедить клиентов купить до $$$x$$$ автомобилей (на выбор Карела), при условии, что это автомобили разных моделей.

Определите минимальное количество клиентов, которое должен привлечь Карел, чтобы продать все автомобили.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 5 \cdot 10^5$$$; $$$1 \le x \le 10$$$) — количество различных моделей автомобилей и максимальное количество автомобилей, которое Карел может убедить клиента купить.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество автомобилей каждой модели.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимально возможное количество клиентов, необходимое для продажи всех автомобилей.

Пример
Входные данные
4
3 2
3 1 2
3 3
2 1 3
5 3
2 2 1 9 2
7 4
2 5 3 3 5 2 5
Выходные данные
3
3
9
7
Примечание

В первом наборе входных данных Карелу всего нужно привлечь $$$3$$$ покупателя. Он убедит покупателей купить следующие модели автомобилей:

  • Клиент $$$1$$$ купит $$$2$$$ автомобиля моделей $$$1$$$ и $$$3$$$.
  • Клиент $$$2$$$ купит $$$2$$$ автомобиля моделей $$$1$$$ и $$$2$$$.
  • Клиент $$$3$$$ купит $$$2$$$ автомобиля моделей $$$1$$$ и $$$3$$$.

Во втором наборе входных данных Карелу нужно всего привлечь $$$3$$$ покупателя. Он убедит покупателей купить следующие модели автомобилей:

  • Клиент $$$1$$$ купит $$$2$$$ автомобиля моделей $$$1$$$ и $$$3$$$.
  • Клиент $$$2$$$ купит $$$3$$$ автомобиля моделей $$$1$$$, $$$2$$$ и $$$3$$$.
  • Клиент $$$3$$$ купит $$$1$$$ автомобиль модели $$$3$$$.