SW 역량 테스트

SW 역량 테스트는 총 $T$분 동안 진행되고, 문제는 $N$개가 나온다. 시험이 진행되는 동안 아무 때나 소스 코드를 제출할 수 있다.

$i$번 문제를 $t$분에 맞히면 $M_i - t \times P_i$점을 받는다. 응시자가 $i$번 문제를 푸는 데 걸리는 시간은 $R_i$분이다.

응시자는 한 번에 한 문제만 풀고, 풀기 시작한 문제는 중간에 멈추지 않는다. 어떤 문제를 어떤 순서로 풀지는 자유롭게 정하고, 풀지 않고 넘기는 문제가 있어도 된다. 시험이 시작한 시각을 0분이라고 하면, 푼 문제를 순서대로 이어 붙였을 때 마지막 문제를 맞히는 시각도 $T$분을 넘을 수 없다.

최종 점수는 맞힌 문제의 점수를 모두 더한 값이고, 한 문제도 풀지 않으면 0점이다. 응시자가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $T$가 주어진다. ($1 \le N \le 50$, $1 \le T \le 100\,000$)

둘째 줄에 $M_1, M_2, \ldots, M_N$이, 셋째 줄에 $P_1, P_2, \ldots, P_N$이, 넷째 줄에 $R_1, R_2, \ldots, R_N$이 공백으로 구분되어 주어진다. ($1 \le M_i, P_i, R_i \le 100\,000$)

첫째 줄에 응시자가 얻을 수 있는 점수의 최댓값을 출력한다.