Ya vamos llegando a Péeeenjamoo ♫♫♫

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:

• Another family member is seated in the same row as them, or
• They are sitting alone in their row (with an empty seat next to them).

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 um_{i=1}^{n}a_i \le 2r$.

Input

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.

Output

For each test case, output the maximum number of happy people in an optimal seating arrangement.

Note

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.

In the second test case, a possible seating arrangement with $6$ happy people is shown below.

In the third test case, a possible seating arrangement with $6$ happy people is shown below.

Samples

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