Codeforces Round 978 (Div. 2) |
---|
Закончено |
В Пенхамо едут $$$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$$$) — количество членов семьи в каждой семье.
Для каждого набора входных данных выведите максимальное количество счастливых людей при оптимальной рассадке.
43 32 3 13 32 2 24 51 1 2 24 53 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}{}$$$ |
Название |
---|