THỰC HÀNH

Tỉnh Sơn La đang triển khai rất nhiều dự án xây dựng cơ sở hạ tầng cho Thành Phố. Tập đoàn xây dựng XYZ nhận được lời mời thầu n dự án (đánh số từ 1 đến n). Sau khi tính toán thì tập đoàn này thấy để xây dựng dự án thứ i sẽ cần số vốn là c_i và sau khi hoàn thành sẽ thu hồi được vốn và thu được lợi nhuận là p_i. Tập đoàn này có thể chọn thầu một số dự án bất kỳ trong danh sách trên và với những dự án được chọn, tập đoàn này phải bỏ toàn bộ vốn ra xây dựng và khi hoàn thành mới được thanh toán toàn bộ.

Hiện tại, tập đoàn XYZ đang có số vốn là S. Bạn hãy lập chương trình giúp cho tập đoàn này lựa chọn các dự án để nhận thầu sao cho có đủ vốn để xây dựng các dự án này và thu về lợi nhuận lớn nhất có thể nhé.

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 c₁, c₂, …, c_n.
• Dòng thứ ba chứa n số nguyên dương p₁, p₂, …, p_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à lợi nhuận lớn nhất có thể đượ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 thầu dự án số 3 thì có đủ vốn để xây dựng và thu được lợi nhuận là 8 (Nếu chọn thầu dự án số 1 và 2 thì cũng đủ vốn để xây dựng nhưng chỉ thu được lợi nhuận là 7).

Giới hạn:1 ≤ n ≤ 25; 1 ≤ S ≤ 30000; 1 ≤ c_i, p_i ≤ 10000