Codeforces Round 978 (Div. 2) |
---|
Finished |
There are $$$n$$$ families travelling to Pénjamo to witness Mexico's largest-ever "walking a chicken on a leash" marathon. The $$$i$$$-th family has $$$a_i$$$ family members. All families will travel using a single bus consisting of $$$r$$$ rows with $$$2$$$ seats each.
A person is considered happy if:
Determine the maximum number of happy people in an optimal seating arrangement. Note that everyone must be seated in the bus.
It is guaranteed that all family members will fit on the bus. Formally, it is guaranteed that $$$\displaystyle\sum_{i=1}^{n}a_i \le 2r$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$r$$$ ($$$1 \le n \le 100$$$; $$$1 \le r \le 500$$$) — the number of families and the number of rows in the bus.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10$$$) — the number of family members in each family.
For each test case, output the maximum number of happy people in an optimal seating arrangement.
43 32 3 13 32 2 24 51 1 2 24 53 1 1 3
4 6 6 6
In the first test case, the two members of the first family can sit together in the first row, while the two members of the second family can sit together in the second row. The remaining member of the second family can sit in the third row along with a member of the third family. This seating arrangement is shown below, where the $$$4$$$ happy people are colored green.
$$$\color{green}{1}$$$ | $$$\color{green}{1}$$$ |
$$$\color{green}{2}$$$ | $$$\color{green}{2}$$$ |
$$$2$$$ | $$$3$$$ |
In the second test case, a possible seating arrangement with $$$6$$$ happy people is shown below.
$$$\color{green}{3}$$$ | $$$\color{green}{3}$$$ |
$$$\color{green}{1}$$$ | $$$\color{green}{1}$$$ |
$$$\color{green}{2}$$$ | $$$\color{green}{2}$$$ |
In the third test case, a possible seating arrangement with $$$6$$$ happy people is shown below.
$$$\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}{}$$$ |
Name |
---|