#1072 · STARF

“Ă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 đó.