Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Trong siêu thị có ~n~ ~(0 < n \le 1000)~ đồ vật, đồ vật thứ ~i~ có trọng lượng là ~w[i]~, ~0 < w[i] \le 1000~ và giá trị là ~v[i]~, ~0 < v[i] \le 10^9~. Các mặt hàng ở đây có thể coi số lượng là vô hạn.

Một tên trộm đột nhập vào siêu thị, tên trộm mang một cái túi có thể chứa tối đa là ~M~, lần này với các đồ vật có số lượng thoải mái nên tên trộm không áp dụng được kỹ thuật chọn như trước nữa để lấy được nhiều giá trị nhất mà tổng khối lượng không vượt quá chiếc túi. Chắc hẳn, sẽ tồn tại một cách lựa chọn thông minh khác.

Yêu cầu: Hãy chọn các vật sao cho đặt vừa trong chiếc túi mà tổng giá trị lớn nhất có thể. Mỗi vật có thể được chọn nhiều lần.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~M~ ~(0 < n \le 10^3,\ 0 < M \le 10^4)~.
• ~n~ dòng tiếp theo mỗi dòng ghi 2 số nguyên ~v_i~ và ~w_i~ là giá trị và trọng lượng của đồ vật thứ ~i~.

Kết quả

• Ghi ra giá trị lớn nhất của các đồ vật mà tên trộm có thể lấy.

Giới hạn

• ~0 < n \le 1000~, ~0 < M \le 10^4~, ~0 < w_i \le 1000~, ~0 < v_i \le 10^9~.
• Time limit: 1 giây. Memory limit: 16MB (đề gốc là 4MB – bảng QHĐ 2 chiều sẽ bị tràn bộ nhớ).

Sample Input 1

3 45
40 12
60 20
50 15

Sample Output 1

150

Giải thích

Lấy 3 cái đồ vật thứ 3: tổng trọng lượng ~3 \cdot 15 = 45 \le 45~, tổng giá trị ~3 \cdot 50 = 150~. Các cách khác như ~12 + 12 + 20 = 44~ (giá trị ~140~) hay ~20 + 20 = 40~ (giá trị ~120~) đều không bằng.