题目描述

前往佩尼亚莫的巴士

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$ ）。( $1 \le a_i \le 10$ ) - 每个家庭的家庭成员数。

输出格式

针对每个测试案例，输出最佳座位安排下最多可容纳的人数。

说明/提示

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

在第二个测试案例中，有 $6$ 个快乐的人的可能座位安排如下所示。

在第三个测试案例中，有 $6$ 个快乐的人的可能座位安排如下所示。

样例

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