Một nhà máy chế biến sữa cần mua hàng ngày N lít sữa của M nông dân. Mỗi nông dân có thể cung cấp một lượng sữa và đưa ra giá bán sữa khác nhau.
Hãy tìm cách mua sữa sao cho đủ số lượng sữa cần cho hàng ngày với số tiền bỏ ra là ít nhất. Biết rằng tổng lượng sữa của các nông dân luôn đủ cung cấp cho nhà máy.
Dữ liệu vào:
Kết quả:
Milk.inp |
Milk.out |
Giải thích |
100 5 5 20 9 40 3 10 8 80 6 30 |
630 |
Mua 20 lít sữa của nông dân 1 => 5*20 = 100 Không mua sữa của nông dân 2 Mua 10 lít sữa của nông dân 3 => 3*10 = 30 Mua 40 lít sữa của nông dân 4 => 8*40 = 320 Mua 30 lít sữa của nông dân 5 => 6*30 = 180 Tổng số tiền mua = 100 + 30 + 320 + 180 = 630 |