Bài toán cái túi

Sắp tới, Alice cùng Bob sẽ đi dã ngoại cùng với lớp. Để chuẩn bị cho chuyến đi này Alice đã mua cho mình một chiếc túi siêu to khổng lồ có khả năng chứa $H$ kilogram và nhờ Bob chọn các đồ vật cần thiết nhất để mang đi dã ngoại.

Có tất cả $n$ đồ vật, mỗi đồ vật đều có một độ nặng là $W_i$ kilogram và độ cần thiết là $V_i$. Bob cần chọn một số đồ vật (mỗi đồ vật chọn nhiều nhất một lần, có thể không chọn đồ vật nào) để cho vào chiếc túi mà Alice mua sao cho tổng độ nặng của các vật Bob chọn không được vượt quá $H$ và tổng độ cần thiết của các vật đó là lớn nhất có thể.

Bob vẫn chưa thể tìm được cách tối ưu nhất để chọn các đồ vật, các bạn hãy giúp Bob nhé.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $T$ là số bộ test ($1\le T\le 10$).
• Các dòng sau gồm $T$ bộ test, mỗi bộ test được miêu tả bằng $3$ dòng:
  • Dòng đầu tiên gồm hai số nguyên $n$ và $H$ lần lượt là số lượng đồ vật và khả năng chứa của túi đồ.
  • Dòng thứ hai gồm $n$ số nguyên dương $W_1,W_2,\dots ,W_n$, trong đó $W_i$ là độ nặng của vật thứ $i$.
  • Dòng thứ ba gồm $n$ số nguyên dương $V_1,V_2,\dots ,V_n$, trong đó $V_i$ là độ cần thiết của vật thứ $i$.

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng là tổng độ cần thiết lớn nhất có thể của bộ test tương ứng.

Ràng buộc

• $1\le T\le 10$.
• $1\le n\le 40$.
• $1\le W_i\le {10}^{12}$, $1\le H\le {10}^{12}$.
• $1\le V_i\le {10}^{12}$.

Subtasks

• Subtask 1 ($10\%$ số test): $n\le 18$, $W_i\le {10}^{12}$, $H\le {10}^{12}$.
• Subtask 2 ($20\%$ số test): $n\le 40$, $W_i\le 1000$, $H\le 1000$.
• Subtask 3 ($70\%$ số test): $n\le 40$, $W_i\le {10}^{12}$, $H\le {10}^{12}$.

Ví dụ