Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0229 - ГЕНРИ ФОРД

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

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

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

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

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

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

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

Примеры

stdin

stdout

1

1
2 1
2 2

2


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.East Sibirean QF 2014.F

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.