“Ăn một quả trả cục vàng

May túi ba gang mang đi mà đựng”

Bảo Bay Bổng đã nghe câu chuyện cây khế từ thuở ấu thơ và cậu vô cùng thích thú với nó. Vì thế hôm nay cậu đã quyết định lên đường tới đảo giấu vàng.

Trên hòn đảo có n cục vàng, cục vàng thứ i có cân nặng w_i và có giá trị v_i. Cậu mang theo một chiếc túi có thể chứa được cân nặng tối đa là S. Khác với câu chuyện được nghe, Bảo sẽ chèo thuyền ra đảo giấu vàng. Vì thế, cậu có thể tự chèo ra đảo hoặc tự chèo về một số lần tuỳ ý. Cậu nghĩ ra một cách để lấy được nhiều vàng đó là cậu sẽ ra đảo, lấy vàng cho vào túi rồi đem về nhà, bỏ bớt ra khỏi túi cho túi đỡ nặng rồi lại chèo ra đảo lấy thêm vàng về. Hãy cho biết Bảo Bay Bổng có thể đem về nhà tối đa lượng vàng có giá trị là bao nhiêu?

Dòng đầu chứa số nguyên dương q (1 \leq q \leq 5) — số truy vấn. Trong mỗi truy vấn:

• Dòng đầu tiên chứa hai số nguyên dương n, S (1 \leq n \leq 10^5; 1 \leq S \leq 10^9).
• Dòng thứ hai chứa n số nguyên dương w_1, w_2,..., w_n (1 \leq w_i \leq 10^9).
• Dòng thứ ba chứa n số nguyên dương v_1, v_2,..., v_n (1 \leq v_i \leq 10^9)

Với mỗi truy vấn, in ra trên một dòng một số nguyên không âm là kết quả của truy vấn đó.

• Trong truy vấn đầu tiên, Bảo đi ra đảo hai lần: Lần thứ nhất ra đảo cậu đem về cục vàng thứ 1 và cục vàng thứ 2. Lần thứ hai ra đảo cậu đem về cục vàng thứ 3. Tổng giá trị nhận được là: 1 + 2 + 3 = 6.
• Trong truy vấn thứ hai, Bảo đi ra đảo ba lần: Lần thứ nhất cậu đem về cục vàng thứ 1 và cục vàng thứ 4. Lần thứ hai cậu đem về cục vàng thứ 2 và cục vàng thứ 3. Lần thứ ba cậu đem về cục vàng thứ 5. Cục vàng thứ 6 và thứ 7 không thể mang về do vượt quá trọng lượng cho phép của túi. Tổng giá trị nhận được là: 2 + 2 + 2 + 2 + 2 = 10.