Atêna, đứa con được thần Dớt sinh ra từ đầu của mình, là một vị nữ thần của Trí tuệ, Tri thức và Chiến trận. Nàng đã sáng tạo ra N loại bảo bối khác nhau. Bảo bối thứ i có trọng lượng wi và sức mạnh chiến đấu là pi (i N =1.. ) . Số lượng mỗi loại bảo bối là không hạn chế.
Trước mỗi trận chiến, để giành được chiến thắng, Atêna cần chọn M bảo bối để mang theo sao cho tổng trọng lượng đúng bằng W và tổng sức mạnh đúng bằng P . Nếu không chọn được thì trận chiến được hoãn lại và khi đó M được đặt bằng 0.
Yêu cầu: Hãy xác định giá trị M nhỏ nhất là bao nhiêu?
Dữ liệu: Đọc vào từ tệp văn bản WPM.INP có cấu trúc như sau:
- Dòng đầu ghi lần lượt ba số n, p, w (0 < n < 21;0 < p, w <150) ;
- N dòng tiếp theo, dòng thứ i ghi lần lượt hai số Pi và Wi (0 < Pi , Wi <150) ;
- Các số trên cùng một dòng cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản WPM.OUT gồm một số duy nhất là giá trị M tìm được.
Ví dụ: WPM.INP WPM.INP
3 11 17 0
12 3
4 7
8 10
WPM.INP WPM.INP
4 9 17 4
1 2
2 3
3 6
4 10
Phương án tối ưu trong ví dụ trên được thực hiện như sau:
- chọn bảo bối thứ 1 với số lượng 1 cái có được sức mạnh 1 và trọng lượng 2;
- chọn bảo bối thứ 2 với số lượng 1 cái có được sức mạnh 2 và trọng lượng 3;
- chọn bảo bối thứ 3 với số lượng 2 cái có được sức mạnh 6 và trọng lượng 12.
