Пограбування
У центрі Бухареста знаходиться величезний банк із великим сховищем. У цьому сховищі розміщено N великих коробок, пронумерованих від 1 до N. У коробці з номером k знаходяться k діамантів, кожен з яких має вагу W_k та вартість C_k.
Джон і Брус зараз у сховищі. Вони хотіли б забрати всі діаманти, але можуть нести лише ті, чия загальна вага не перевищує M.
Ваше завдання — допомогти Джону і Брусу вибрати діаманти так, щоб їх загальна вага була меншою або рівною M, а загальна вартість — максимально можливою.
Вхідні дані
Перша строка містить одне ціле число T — кількість тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа N і M, розділені пробілом. Наступний рядок містить N цілих чисел W_k, розділених пробілом. Наступний рядок містить N цілих чисел C_k, розділених пробілом.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить максимально можливу загальну вартість діамантів.
Обмеження
1 <= T <= 74,
1 <= N <= 15,
1 <= M <= 1000000000 (10^9),
1 <= W_k, C_k <= 1000000000 (10^9).