[소프티어 Level2] 금고털이(Java)

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int W = Integer.parseInt(s[0]);
        int N = Integer.parseInt(s[1]);

        PriorityQueue <int []> metals = new PriorityQueue<>((o1, o2) -> o1[1] < o2[1] ? 1:-1);

        for(int i = 0; i < N; i++){
            String[] str = br.readLine().split(" ");
            metals.add(new int[]{Integer.parseInt(str[0]), Integer.parseInt(str[1])});
        }
        int sum = 0;

        while(!metals.isEmpty()){
            int[] e = metals.poll();
            if(W > e[0]) // 배낭이 여유가 있으면
            {
                sum += e[1] * e[0];
                W -= e[0]; // 다 담기
            }
            else
            {
                sum += W * e[1];
                break;
            }
        }
        System.out.println(sum);
    }
}