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 dự án (đánh số từ đến ). Sau khi tính toán thì tập đoàn này thấy để xây dựng dự án thứ sẽ cần số vốn là và sau khi hoàn thành sẽ thu hồi được vốn và thu được lợi nhuận là . 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ộ cả vốn lẫn lời.
Hiện tại, tập đoàn XYZ đang có số vốn là . 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 và ;
Dòng thứ hai chứa số nguyên dương ;
Dòng thứ ba chứa số nguyên dương .
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ố thì có đủ vốn để xây dựng và thu được lợi nhuận là (Nếu chọn thầu dự án số và thì cũng đủ vốn để xây dựng nhưng chỉ thu được lợi nhuận là ).
