Câu 4. MUA HÀNG (4,0 điểm; Đề TS vào 10 – Khoa học Huế 2026 – 2027 vòng 2)

Phúc nhận được một phiếu mua hàng khuyến mãi nhân dịp lễ 30/4 và Quốc tế lao động 1/5 tại siêu thị Aeon Mall. Phúc có thể chọn một số loại hàng hóa để mua trong N loại hàng hóa được đánh số từ 1 đến N (N ≤ 1000), hàng hóa thứ i có trọng lượng W_i (W_i ≤ 100) và giá trị V_i (V_i ≤ 1000).
Tuy nhiên, siêu thị Aeon Mall quy định khách hàng có phiếu mua hàng khuyến mãi chỉ được dùng một xe đẩy có trọng lượng M (M ≤ 1000). Hỏi Phúc sẽ chọn những hàng hóa nào để được tổng giá trị lớn nhất mà không vượt quá trọng lượng M của xe đẩy (mỗi hàng hóa chỉ chọn 1 lần).
Yêu cầu: Hãy cho biết tổng giá trị hàng hóa lớn nhất mà Phúc có thể chọn được.
Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương N (N ≤ 1000) và M (M ≤ 1000).
• N dòng tiếp theo, dòng thứ i (i = 1..N) ghi hai số nguyên dương W_i (W_i ≤ 100) và V_i (V_i ≤ 1000).

Dữ liệu ra: Thông báo ra màn hình một số nguyên duy nhất là tổng giá trị hàng hóa lớn nhất mà Phúc chọn được.
Ví dụ: