有 $$$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}$$$$$$\颜色{绿色}{}$$$$$$\颜色{绿色}{}$$$$$$\颜色{绿色}{}$$$