Book Shop

You are in a book shop which sells $n$ different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most $x$. What is the maximum number of pages you can buy? You can buy each book at most once.

Input

The first line contains two integers $n(1\le n\le 1000)$ and $x(1\le x\le 10^5)$: the number of books and the maximum total price.

The next line contains $n$ integers $h_1,h_2,...,h_n(1\le h_i\le 1000)$: the price of each book.

The last line contains $n$ integers $s_1,s_2,...,s_n(1\le s_i\le 1000)$: the number of pages of each book.

Output

Print one integer — the maximum number of pages.

Examples

Note

You can buy books $1$ and $3$. Their price is $4+5=9$ and the number of pages is $5+8=13$.