강도 사건

부쿠레슈티 시내에는 아주 큰 금고를 갖춘 아주 큰 은행이 있다. 금고 안에는 1번부터 $N$번까지 번호가 매겨진 아주 큰 상자 $N$개가 있다. $k$번 상자 안에는 아주 큰 다이아몬드가 정확히 $k$개 들어 있으며, 그 상자에 있는 다이아몬드는 모두 무게가 $W_k$, 값어치가 $C_k$이다.

지금 John과 Brus가 금고 안에 있다. 그들은 모든 것을 훔치고 싶지만, 안타깝게도 무게의 합이 $M$을 넘지 않는 만큼만 다이아몬드를 들고 나올 수 있다.

$k$번 상자에서는 0개부터 최대 $k$개까지 원하는 만큼 다이아몬드를 가져갈 수 있다. 무게의 합이 $M$ 이하이면서 값어치의 합이 최대가 되도록 다이아몬드를 고르는 것을 도와주어라.

첫째 줄에는 정수 $T$ — 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 공백 하나로 구분된 두 정수 $N$과 $M$이 있는 줄로 시작한다. 다음 줄에는 $N$개의 정수 $W_k$가 공백 하나로 구분되어 주어진다. 그다음 줄에는 $N$개의 정수 $C_k$가 공백 하나로 구분되어 주어진다.

각 테스트 케이스마다, 훔칠 수 있는 다이아몬드 값어치 합의 최댓값을 한 줄에 출력한다.

• $1 \le T \le 74$
• $1 \le N \le 15$
• $1 \le M \le 10^9$
• $1 \le W_k, C_k \le 10^9$