USACO Training: Mixing Milk fails on the last Case
<p><em>Here is the Mixing Milk Problem</em></p>

<p>The Merry Milk Makers company buys milk from farmers, packages it into attractive 1- and 2-Unit bottles, and then sells that milk to grocery stores so we can each start our day with delicious cereal and milk.</p>

<p>Since milk packaging is such a difficult business in which to make money, it is important to keep the costs as low as possible. Help Merry Milk Makers purchase the farmers' milk in the cheapest possible manner. The MMM company has an extraordinarily talented marketing department and knows precisely how much milk they need each day to package for their customers.</p>

<p>The company has contracts with several farmers from whom they may purchase milk, and each farmer has a (potentially) different price at which they sell milk to the packing plant. Of course, a herd of cows can only produce so much milk each day, so the farmers already know how much milk they will have available.</p>

<p>Each day, Merry Milk Makers can purchase an integer number of units of milk from each farmer, a number that is always less than or equal to the farmer's limit (and might be the entire production from that farmer, none of the production, or any integer in between).</p>

<p><strong>Given</strong>:</p>

<p>The Merry Milk Makers' daily requirement of milk
The cost per unit for milk from each farmer
The amount of milk available from each farmer
calculate the <strong>minimum</strong> amount of money that Merry Milk Makers must spend to meet their daily need for milk.</p>

<p><strong>Line 1:   Two integers, N and M.</strong> <br></p>

<p>The first value, N, (0 &lt;= N &lt;= 2,000,000) is the amount of milk that Merry Milk Makers wants per day. 
The second, M, (0 &lt;= M &lt;= 5,000) is the number of farmers that they may buy from. <br></p>

<p><strong>Lines 2 through M+1:</strong>    </p>

<p>The next M lines each contain two integers: Pi and Ai. 
Pi (0 &lt;= Pi &lt;= 1,000) is price in cents that farmer i charges.
Ai (0 &lt;= Ai &lt;= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.</p>

<hr>

<p><strong>My Solution</strong>:</p>

<p>My solution was to store the farmers' prices of milk and the quantities of milk they have in a <code>HashMap</code>. As long as there was still milk to buy, I would add the lowest price * the quantity of the lowest price of milk from the <code>HashMap</code> to the cost, as I sorted an <code>ArrayList</code> that stored the costs of milk. Because it is possible that more milk is purchased than needed, I have an <code>if statement</code> that checks that if more milk is purchased than needed, the extra cost is subtracted. I then remove the lowest price from the <code>ArrayList</code></p>

<p><strong>Code</strong>:</p>

<p>The code works for all of the test cases, except from the last one, where there is too much data to put in the question so I'll have it linked to a Google Document.</p>

<p>Input and Output: <a href="https://docs.google.com/document/d/10I3b0z17kP_LZzD2lBlH-Igoe6NPybZleD9tNYonqSQ/edit?usp=sharing" rel="nofollow">https://docs.google.com/document/d/10I3b0z17kP_LZzD2lBlH-Igoe6NPybZleD9tNYonqSQ/edit?usp=sharing</a></p>

<pre><code>/*
ID: henry.d2
LANG: JAVA
TASK: milk
*/

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class milk
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new FileReader("milk.in"));

        String[] components = br.readLine().split(" ");

        int n = Integer.parseInt(components[0]); // Get the amount of milk that Merry Milk Makers wants per day (N)
        int m = Integer.parseInt(components[1]); // Get the number of farmers that they may buy from (M)

        Map&lt;Integer, Integer&gt; farmerAndPrice = new HashMap&lt;Integer, Integer&gt;(); // HashMap that stores the prices of milk and quantities
        List&lt;Integer&gt; prices = new ArrayList&lt;Integer&gt;(); // ArrayList that stores the prices for milk

        // Read in P(i) (The price in cents that farmer i charges) and A(i) (The amount of milk that farmer i can send to MMM per day)
        for (int i = 0; i &lt; m; i++)
        {
            String[] pAndA = br.readLine().split(" ");

            int Pi = Integer.parseInt(pAndA[0]);
            int Ai = Integer.parseInt(pAndA[1]);

            farmerAndPrice.put(Pi, Ai); // Add price and quantity to HashMap
            prices.add(Pi); // Add price to ArrayList
        }

        Collections.sort(prices);

        int milkToBuy = 0;
        int cost = 0;

        while (milkToBuy &lt; n) // The farmers still have milk to buy from
        {
            cost += farmerAndPrice.get(prices.get(0)) * prices.get(0);
            milkToBuy += farmerAndPrice.get(prices.get(0));

            if (milkToBuy &gt; n) // If we buy more milk than we need
            {
                cost -= (milkToBuy - n) * prices.get(0);
            }

            System.out.println(prices.toString());

            prices.remove(0);
        }

        File file = new File("milk.out"); // Output to milk.out
        PrintWriter printWriter = new PrintWriter(file);

        printWriter.println(cost);

        printWriter.close();
    }
}
</code></pre>