소프티어

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

bool CompareBySecond(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return a.second > b.second;
}

int main(int argc, char** argv)
{
    std::vector<std::pair<int,int>> goldVec;
    int result = 0;
    int bag = 0;
    int totalN = 0;
    cin >> bag >> totalN;

    for(int i = 0; i < totalN; ++i)
    {
        int a,b;
        cin >> a >>b;
        std::pair<int,int> goldPair(a,b);
        goldVec.emplace_back(goldPair);
    }

    // 오름차순으로 정렬
    std::sort(goldVec.begin(), goldVec.end(), CompareBySecond);

    for(const auto& iter : goldVec)
    {
        const int gram = iter.first;
        const int value = iter.second;
        
        int remain = bag - gram;
        if(remain <= 0)
        {
            result += bag * value;
            break;
        }
        else
        {
            result += gram * value;
            bag -= gram;
        }
    }

    cout << result;
    return 0;
}