Làm bài tập


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.