Trong một trường học có n lớp (mỗi lớp gồm cả nam lẫn nữ). Lớp học i có ~a_i~ thành viên. Tất cả trường đi du lịch bằng xe du lịch, các xe được bố trí có r hàng ghế và mỗi hàng ghế 2 bạn ngồi. Hạnh phúc nhất là khi:

• Một thành viên khác trong lớp ngồi cùng hàng với họ, hoặc
• Họ ngồi một mình trong hàng của họ (có một ghế trống bên cạnh).

Xác định số lượng người vui vẻ tối đa trong cách sắp xếp chỗ ngồi tối ưu. Lưu ý rằng mọi người phải ngồi trên chuyến xe buýt. Đảm bảo rằng tất cả các thành viên trong lớp sẽ ngồi vừa trên xe buýt. ~\sum_{i=1}^{n}a_{i} ≤ 2r~

Đầu vào:

• gồm t dòng (1 ≤ t ≤ ~10^5~)
• Dòng thứ nhất gồm 2 số n và r (1 ≤ n ≤ 100; 1 ≤ r≤ 500)
• Dòng tiếp theo chứa n số nguyên ~a_1, a_2, .., a_n~ (1 ≤ ~ a_i~ ≤ 10)

Đầu ra:

Hãy đưa ra số lượng người vui vẻ tối đa trong cách sắp xếp chỗ ngồi tối ưu tương ứng với mỗi bộ test

Ví dụ:

Input

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

Output

4
6
6
6