Bài toán cái túi knapsack.cpp/knapsack.pas / Timelimit: 3s

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à Wi kilogram và độ cần thiết là Vi. Bob cần chọn một số đồ vật để 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á ~T~ 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é.

Input

• Dòng đầu tiên: số nguyên ~T~ là số bộ test (~~T~ <= 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 là 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ứ 2 gồm ~n~ số nguyên dương Wi là độ nặng của vật thứ ~i~ Dòng thứ 3 gồm ~n~ số nguyên dương Vi là độ cần thiết của vật thứ ~i~

Output

• Gồm ~T~ dòng, mỗi dòng là tổng độ cần thiết lớn nhất có thể

Sample Input 1

knapsack.inp knapsack.out
1 19
5 16
5 6 12 16 9
8 9 7 9 10
Giải thích:
- Chọn vật thứ 2 và 5
Với tất cả subtask: Vi <= 1012
Sub1 (10%): n≤18, Wi≤1012, H≤1012
Sub2 (20%): n≤40, Wi≤1000, H≤1000
Sub3 (70%): n≤40, Wi≤1012, H≤1012