package pickpocket; import java.io.BufferedReader; import java.io.File; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; class SortbyEfficiancy implements Comparator { @Override public int compare(int[] o1, int[] o2) { // TODO Auto-generated method stub return ((-1)*(o1[1]/o1[0]) - (o2[1]/o2[0])); } } public class pickpockets { public static void main(String[] args) throws IOException { String tmp; String tmpstr[] = new String[2]; int days = 0, sum = 0; List operations = new ArrayList(); BufferedReader reader = new BufferedReader( new InputStreamReader(System.in)); tmp = reader.readLine(); tmpstr = tmp.split(" ", 2); days = Integer.parseInt(tmpstr[0]); int numOfCleanStores [] = new int [days]; tmp = reader.readLine(); tmpstr = tmp.split(" ", -1); for(int i = 0; i < days; i++) { numOfCleanStores[i] = Integer.parseInt(tmpstr[i]); } while((tmp = reader.readLine()) != null) { tmpstr = tmp.split(" "); int [] tmpint = {Integer.parseInt(tmpstr[0]), Integer.parseInt(tmpstr[1])}; operations.add(tmpint); } Collections.sort(operations, new SortbyEfficiancy()); for(int[] asd: operations) { System.out.println(asd[1] + "\t" + asd[2]); } for(int i = 0; i < days; i++) { for(int j = 0; j < operations.size(); j++) { if(operations.get(j)[0] == days -i) if(numOfCleanStores[i] >= 1) { for(int k = i; k < operations.get(j)[0]; k++) { numOfCleanStores[k] -= 1; } sum+= operations.get(j)[1]; operations.remove(j); numOfCleanStores[i] -= 1; } else { if(operations.get(j)[0] <= days - i) { if(numOfCleanStores[i] >= 1) { sum+= operations.get(j)[1]; operations.remove(j); numOfCleanStores[i] -= 1; } } } } } System.out.println(sum); } }