/* ID: karihee1 LANG: JAVA TASK: milk */ /* milk.java * * This is a solution to the 10th USACO Training Problem "Mixing Milk". * A copy of the problem statement can be found here: https://jvonk.github.io/usaco/2018/09/29/milk.html * * The solution below demonstrates sorting an ArrayList containing a custom class * * NOTE: since USACO Trainiing Problems still uses files for input and output, * I have replaced the BufferedReader and PrintWriter lines that use stdin and stdout. * * The file "milk.in" looks like this: * 100 5 * 5 20 * 9 40 * 3 10 * 8 80 * 6 30 */ import java.io.*; import java.util.*; class milk { public static void main (String [] args) throws IOException { //BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); //PrintWriter out = new PrintWriter(System.out); BufferedReader in = new BufferedReader(new FileReader("milk.in")); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("milk.out"))); StringTokenizer st; st = new StringTokenizer(in.readLine()); int N = Integer.parseInt(st.nextToken()); // Milk Demand (0 <= N <= 2,000,000) int M = Integer.parseInt(st.nextToken()); // Number of farmers to buy from (0 <= M <= 5,000) // out.println(N + " " + M); // DEBUGGING PRINT STATEMENT ArrayList<Farmer> al = new ArrayList<Farmer>(M); for (int i=0;i<M;i++) { st = new StringTokenizer(in.readLine()); int P = Integer.parseInt(st.nextToken()); // Price int A = Integer.parseInt(st.nextToken()); // Amount // out.println(P + " " + A); // DEBUGGING PRINT STATEMENT al.add(new Farmer(P,A)); } Collections.sort(al); Farmer f; int answer=0; for (int i=0;i<M; i++) { f = al.get(i); //out.println(f.price + " " + f.amount); // DEBUGGING PRINT STATEMENT if ((N>0) && (f.amount>0)) { // We want to buy from this farmer! if (N>=f.amount) { answer += f.amount * f.price; // buy all from this farmer N -= f.amount; } else { answer += N*f.price; // buy some from this farmer -- demand fulfilled N = 0; } } } out.println(answer); out.close(); } } class Farmer implements Comparable<Farmer> { public int price; public int amount; public Farmer(int price,int amount) { this.price = price; this.amount = amount; } @Override public int compareTo(Farmer obj) { // sort in ascending order. // compareTo returns a negative integer, zero, or a positive integer as // this object is less than, equal to, or greater than the specified object. if (this.price<obj.price) { return -1; } else if (this.price==obj.price) { return 0; } else { return 1; } } }