A. Автобус в Пенхамо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Ya vamos llegando a Péeeenjamoo ♫♫♫

В Пенхамо едут $$$n$$$ семей, чтобы стать свидетелями крупнейшего в Мексике марафона по выгуливанию куриц на поводках. $$$i$$$-я семья состоит из $$$a_i$$$ человек. Все семьи будут путешествовать на одном автобусе, состоящем из $$$r$$$ рядов с $$$2$$$ сиденьями в каждом.

Человек считается счастливым, если:

  • Другой член семьи сидит в том же ряду, что и он; или
  • Он сидит один в своем ряду (рядом с пустым местом).

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

Гарантируется, что все члены всех семей могут поместиться в автобусе. Формально, гарантируется, что $$$\displaystyle\sum_{i=1}^{n}a_i \le 2r$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$r$$$ ($$$1 \le n \le 100$$$; $$$1 \le r \le 500$$$) — количество семей и количество рядов в автобусе.

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

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

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

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

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

$$$\color{green}{1}$$$$$$\color{green}{1}$$$
$$$\color{green}{2}$$$$$$\color{green}{2}$$$
$$$2$$$$$$3$$$

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

$$$\color{green}{3}$$$$$$\color{green}{3}$$$
$$$\color{green}{1}$$$$$$\color{green}{1}$$$
$$$\color{green}{2}$$$$$$\color{green}{2}$$$

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

$$$\color{green}{4}$$$$$$\color{green}{4}$$$
$$$\color{green}{}$$$$$$\color{green}{2}$$$
$$$\color{green}{3}$$$$$$\color{green}{3}$$$
$$$\color{green}{1}$$$$$$\color{green}{}$$$
$$$\color{green}{}$$$$$$\color{green}{}$$$