THỰC HÀNH

Nghé con hôm nay đi tham gia cuộc thi do làng tổ chức. Bài thi của Nghé là cày n thửa ruộng (đánh số từ 1 đến n). Để cày thửa ruộng thứ i Nghé cần thời gian là t_i và nếu cày xong sẽ được số điểm là d_i. Tuy nhiên, Nghé chỉ có tổng thời gian là S để “làm bài”, do vậy Nghé cần lựa chọn những thửa ruộng để cày cho hợp lý. Bạn hãy lập chương trình giúp Nghé lựa chọn các thửa ruộng để cày trong thời gian S sao cho đạt điểm tối đa.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương n và S.
• Dòng thứ hai chứa n số nguyên dương t₁, t₂, …, t_n.
• Dòng thứ ba chứa n số nguyên dương d₁, d₂, …, d_n.

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

Một số nguyên duy nhất là điểm số lớn nhất Nghé có thể đạt được.

Ví dụ:

Dữ liệu vào:
3 10
4 5 7
3 4 8

Dữ liệu ra:
8

Giải thích: chọn cày thửa ruộng số 3 thì sẽ cày xong và đạt số điểm là 8 (Nếu chọn cày thửa ruộng số 1 và 2 thì cũng cày xong nhưng chỉ đạt 7 điểm).

Giới hạn:1 ≤ n ≤ 25; 1 ≤ S ≤ 30000; 1 ≤ t_i, d_i ≤ 10000