P1208 [USACO1.3] Mixing Milk

Because the profit margin in the dairy industry is very low, reducing the price of raw materials (milk) becomes very important. Help Marry Dairy find the optimal milk purchasing plan. Marry Dairy purchases milk from several farmers, and the price offered by each farmer to the dairy processor may be the same. Also, just as each cow can only produce a fixed amount of milk per day, each farmer can provide a fixed amount of milk per day. Each day, Marry Dairy can purchase an integer amount of milk from each farmer, not exceeding that farmer’s maximum daily output. Given Marry Dairy’s daily milk demand, as well as each farmer’s unit price and maximum supply, compute the minimum cost to purchase enough milk. Note: The total daily supply of all farmers is at least Marry Dairy’s demand.

The first line contains two integers $n,m$, representing the total amount of milk needed and the number of farmers. The next $m$ lines each contain two integers $p_i,a_i$, representing the unit price of milk from the $i$-th farmer and the maximum amount of milk the $i$-th farmer can sell in one day.

A single line containing a single integer, representing the minimum cost for Marry Dairy to obtain the required amount of milk.

Constraints For $100\%$ of the testdata: $0 \le n,a_i \le 2 \times 10^6$，$0\le m \le 5000$，$0 \le p_i \le 1000$. Translation adapted from NOCOW. USACO Training Section 1.3. Translated by ChatGPT 5