A. 前往 Pénjamo 的巴士

时间限制：每个测试 $1$ 秒
内存限制：$256$ MB

Ya vamos llegando a Péeeenjamoo ♫♫♫

有 $n$ 个家庭正在前往 Pénjamo，参加墨西哥有史以来规模最大的“牵着鸡散步”马拉松。第 $i$ 个家庭有 $a_i$ 名家庭成员。所有家庭将乘坐同一辆巴士，巴士有 $r$ 排座位，每排有 $2$ 个座位。

如果满足以下条件之一，则认为一个人是快乐的：

• 有另一名家庭成员坐在同一排，或者
• 他们独自坐在一排（旁边的座位是空的）。

在最优的座位安排中，确定快乐人数的最大值。注意，所有人都必须坐在巴士上。

保证所有家庭成员都能坐下。形式化地说，保证 $\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, \dots, a_n$（$1 \le a_i \le 10$），表示每个家庭的成员数量。

输出格式

对于每个测试用例，输出在最优座位安排中快乐人数的最大值。

示例

输入

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

样例解释

在第一个测试用例中，第一个家庭的两名成员可以坐在第一排，第二个家庭的两名成员可以坐在第二排。第二个家庭的剩余一名成员可以与第三个家庭的一名成员一起坐在第三排。下图显示了这种座位安排，其中 $4$ 个快乐的人被标记为绿色。

在第二个测试用例中，一种可以安排出 $6$ 个快乐的人的座位如下所示：

在第三个测试用例中，一种可以安排出 $6$ 个快乐的人的座位如下所示：