Bài toán: Tối đa hóa số trang sách

Đề bài

Bạn ở một cửa hàng sách bán ~ n ~ loại sách khác nhau. Bạn biết giá và số trang của mỗi cuốn sách.

Bạn đã quyết định rằng tổng chi phí của các cuốn sách bạn mua sẽ không vượt quá ~ x ~. Hãy xác định số lượng trang tối đa mà bạn có thể mua, với điều kiện mỗi cuốn sách chỉ được mua một lần.

Input

• Dòng đầu tiên: hai số nguyên ~ n ~ và ~ x ~ (số sách và tổng chi phí tối đa).
• Dòng thứ hai: ~ n ~ số nguyên ~ h_1, h_2, \ldots, h_n ~ (giá của từng cuốn sách).
• Dòng thứ ba: ~ n ~ số nguyên ~ s_1, s_2, \ldots, s_n ~ (số trang của từng cuốn sách).

Output

• Một số nguyên: tổng số trang tối đa mà bạn có thể mua.

Ràng buộc

• ~ 1 \leq n \leq 1000 ~
• ~ 1 \leq x \leq 10^5 ~
• ~ 1 \leq h_i, s_i \leq 1000 ~

Ví dụ

Input:

4 10
4 8 5 3
5 12 8 1

Output:

13

Giải thích:

• Bạn có thể mua sách 1 và sách 3. Giá của chúng là ~ 4 + 5 = 9 ~, và tổng số trang là ~ 5 + 8 = 13 ~.