← 返回题目列表

Codeforces · 2022/A

A. 前往彭哈莫的巴士

中文机器翻译题面 查看原题

有 $$$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$$$) - 每个家庭中的家庭成员数量。

输出

对于每个测试用例,输出最佳座位安排中快乐的人的最大数量。

示例

输入 #1

4
3 3
2 3 1
3 3
2 2 2
4 5
1 1 2 2
4 5
3 1 1 3

输出 #1

4
6
6
6

注意

在第一个测试用例中,第一个家庭的两个成员可以一起坐在第一排,而第二个家庭的两个成员可以一起坐在第二排。第二家庭的剩余成员可以与第三家庭的成员一起坐在第三排。座位安排如下所示,$$$4$$$ 快乐的人被涂成绿色。

$$$\颜色{绿色}{1}$$$$$$\颜色{绿色}{1}$$$$$$\颜色{绿色}{2}$$$$$$\颜色{绿色}{2}$$$$$$2$$$$$$3$$$

在第二个测试用例中,下面显示了 $$$6$$$ 快乐的人可能的座位安排。

$$$\颜色{绿色}{3}$$$$$$\颜色{绿色}{3}$$$$$$\颜色{绿色}{1}$$$$$$\颜色{绿色}{1}$$$$$$\颜色{绿色}{2}$$$$$$\颜色{绿色}{2}$$$

在第三个测试用例中,下面显示了 $$$6$$$ 快乐的人可能的座位安排。

$$$\颜色{绿色}{4}$$$$$$\颜色{绿色}{4}$$$$$$\颜色{绿色}{}$$$$$$\颜色{绿色}{2}$$$$$$\颜色{绿色}{3}$$ $$$$\颜色{绿色}{3}$$$$$$\颜色{绿色}{1}$$$$$$\颜色{绿色}{}$$$$$$\颜色{绿色}{}$$$$$$\颜色{绿色}{}$$$