There are n books in the store. You know the prices and the number of pages for each of the books. You have x dollars in your pocket, so you can’t spend more than x. What is the maximum number of pages you can buy? Note that you can buy each book only once.

Input

The first line of the input contains two integers n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).

The next line contains n space-separated integers (1 ≤ ≤ 1000) the costs of each book.

The third line contains n space-separated integers (1 ≤ ≤ 1000) the number of pages for each book.

Output

The program should print the maximum number of pages you can buy with x.

Examples

Input

Output

4 10
4 8 5 3
5 12 8 1

13

Explanation

You can buy the first and the third books. The cost will be 4 + 5 = 9, while the number of pages will be 5 + 8 = 13.