Для отбора на один из чемпионатов по программированию проводится квалификационный раунд. Вы хотите узнать, сколько людей удачно прошло его, но пока что организаторы выложили только статистику о том, сколько людей решило каждую из задач.
Квалификационный раунд состоял из 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