Làm bài tập
An còn $N$ bài tập chưa hoàn thành. Bài tập thứ $i$ có $a_i$ điểm và cậu sẽ cần $b_i$ thời gian để làm bài. Hiện tại, cậu còn $K$ thời gian để làm.
Hãy giúp An chọn ra các bài tập để làm sao cho số điểm cậu nhận được là lớn nhất.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, K \ (0<N\le 36; 0<K<10^{10})$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (0<a_i<10^9)$;
- Dòng cuối cùng chứa $N$ số nguyên $b_i \ (0<b_i<10^9)$.
Kết quả
- Số điểm lớn nhất có thể đạt được.
Ví dụ
Ví dụ 1
input
3 8
10 20 30
2 4 6
output
40
Comments