SPOJ in Gyumri

    Генри Форд — известный американский автопромышленник и изобретатель. На своих заводах Генри Форд широко использовал разделение труда и постоянно занимался повышением эффективности производства. Совершенствовался процесс производства автомобилей, изобретались новые инструменты. Также высокое внимание уделялось повышению объемов производства отдельных деталей, даже таких простых, как шестеренки.

   На заводе Генри Форда «Хайленд парк» есть N станков, которые производят одинаковые шестеренки. Для каждого станка известно время в минутах, необходимое для производства одной шестеренки. Станки на заводе работают независимо друг от друга.

   Определите минимальное время в минутах, необходимое для производства партии, состоящей из K шестеренок. При этом можно использовать как один станок, так и несколько работающих одновременно станков.

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

   Первая строка входных данных содержит одно натуральное число T – количество тестов (T ≤ 700). Первая строка теста содержит два натуральных числа: N – количество станков (1 ≤ N ≤ 10⁵), и K – требуемое количество шестеренок (1 ≤ K ≤ 10⁹). Вторая строка теста содержит N натуральных чисел t_i – время в минутах, необходимое i-му станку для производства одной шестеренки. Числа разделены одним пробелом и не превышают 10⁹. Гарантируется, что сумма всех N во входном файле не превосходит 2*10⁹).

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

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

Примеры