Квалификация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

Квалификационный раунд состоял из p задач. Задачу i решили si участников. Чтобы пройти квалификацию, участники должны были решить как минимум k задач. Ваша задача — выяснить, используя только эту информацию, максимальное число участников, которые могли пройти квалификацию.

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

Первая строка ввода содержит количество тестов t. Далее t строк содержат описание тестов. Каждый из них содержит сначала числа p и k, и затем p целых чисел si.

Ограничения: 1 ≤ t ≤ 100, 1 ≤ c ≤ p.

В задаче 1: 1 ≤ p ≤ 6, 0 ≤ si ≤ 1000.

В задаче 2: 1 ≤ p ≤ 60, 0 ≤ si ≤ 1017.

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

Для каждого теста выведите одно число: максимальное число участников, которые могли пройти квалификацию (другими словами, максимальное количество участников которые могли бы решить по не менее k задач).

Примеры тестов

Входные данные
2
2 2 73 100
3 2 245 272 238
Выходные данные
73
377