Hầm vàng không kề nhau

Trong một hầm mỏ hẹp chỉ đi được một chiều có \(N\) đống vàng xếp thành hàng, đống thứ \(i\) nặng \(w_i\) gam. Có một lời nguyền: nếu lấy vàng từ hai đống liền kề nhau thì hầm sẽ sập, nên các đống được lấy không được có hai đống nào kề nhau. Người thợ chỉ mang một chiếc túi chịu được tổng trọng lượng tối đa \(K\) gam.

Với mỗi bộ dữ liệu, hãy tìm tổng trọng lượng vàng lớn nhất mà người thợ có thể mang về (mỗi đống hoặc lấy nguyên hoặc bỏ nguyên), thoả mãn cả hai điều kiện: không lấy hai đống kề nhau, và tổng không vượt quá \(K\). Có thể không lấy đống nào (tổng bằng \(0\)).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa \(N\) và \(K\); dòng thứ hai chứa \(N\) số nguyên \(w_1, w_2, \dots, w_N\).

Output

In ra \(T\) số nguyên trên một dòng, cách nhau bởi dấu cách; số thứ \(j\) là đáp án của bộ dữ liệu thứ \(j\).

Constraints

• \(1 \le T \le 20\)
• \(1 \le N, K, w_i \le 2020\)

Sample Input

3
5 20
8 5 9 7 6
4 9
10 4 4 10
6 30
11 12 13 14 15 16

Sample Output

17 4 30

Explanation

Bộ 1: các lựa chọn không kề nhau như \(\{1,3\}\) cho \(8+9=17\), \(\{2,4\}\) cho \(12\), \(\{3,5\}\) cho \(15\); còn \(\{1,3,5\}\) nặng \(23>20\). Đáp án là \(17\). Bộ 2: hai đống nặng \(10\) vượt quá \(K=9\), và các cặp còn lại đều nặng quá hoặc kề nhau nên chỉ lấy được một đống nặng \(4\). Bộ 3: lấy đống 4 và đống 6 được \(14+16=30\).