URI Online Judge | 2563

Transfer to the Professor

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

Analógimôn Go! is a very popular game. During his quest, the player travels across many cities capturing virtual little monsters called analógimôns.

You are an expert player and have captured N analógimôns so far, numbered from 1 to N. You captured so many monsters that it is getting hard to carry all of them during your journey. However, you can get rid of some of them by transferring them to the Professor.

When you transfer the analógimôn i (for 1 ≤ iN) to the Professor, you earn Di candies in exchange. Since candies are really important items in the game, you want to transfer as many analógimôns as possible to maximize the amount of candies you will earn!

However, analógimôn i (for 1 ≤ iN) weights Pi kg, and, due to a space limitation in Professor’s lab, he cannot accept analógimôns which total sum of their weights exceeds K kg.

Your task is to determine the maximum amount of candies you can obtain by transferring your little monsters, respecting the space limitation in Professor’s lab.


The input contains several test cases. The first line of each test case contains integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 104), the number of analógimôns you captured and the capacity of the Professor’s lab, in kg, respectively. Second line contains N integers D1, ..., DN (1 ≤ Di ≤ 104), indicating how many candies you will obtain by transferring each analógimôn. Third line contains N integers P1, ..., PN (1 ≤ Pi ≤ 104) indicating the weight of each analógimôn, in kg.

The input ends with end-of-file (EOF).


For each test case, print a single line containing the maximum amount of candies you can obtain.

Input Sample Output Sample

4 52
1 8 14 22
4 12 20 30
3 2
9 5 2
12 8 42