Làm bài thi

Trong đề kiểm tra có \(N\) câu hỏi được đánh số từ \(1\) đến \(N\). Câu hỏi thứ \(i\) cần thời gian hoàn thành là \(T_i\) và số điểm đạt được là \(D_i\) (\(1 \le i \le N\)).

Yêu cầu: Tổng thời gian làm bài thi là \(S\). Hãy xác định tổng điểm lớn nhất có thể đạt được nếu có phương án làm bài tối ưu.

Input

• Dòng đầu ghi hai số nguyên dương \(N\) và \(S\);
• Dòng thứ hai ghi \(n\) số nguyên \(T_1,T_2,...,T_N\);
• Dòng thứ ba ghi \(n\) số nguyên \(D_1,D_2,...,D_N\);
• Các được ghi số cách nhau một dấu cách.

Output

• Một dòng ghi số nguyên \(M\) là tổng điểm lớn nhất có được.

Example

3 10
4 5 7
3 4 8

8

Scoring

• \(1 \le N \le 20\);
• \(1 \le S \le 30 000\);
• \(1 \le T_i, D_i \le 10 000\).