CF1379C AC

// Problem: C. Choosing flowers
// Contest: Codeforces - Codeforces Round 657 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1379/C
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;
using a2l = array<ll, 2>;

int t, n, m;

int main(int argc, char **argv)
{
    cin >> t;
    while (t--) {
        cin >> n >> m;
        vector<a2l> vr(m);
        vector<ll> vl(m);
        dbg(n, m);
        for (int i = 0; i < m; ++i)
            cin >> vr[i][1] >> vr[i][0], vl[i] = vr[i][1];
        sort(vr.rbegin(), vr.rend()), sort(vl.begin(), vl.end());
        ll acc = 0, ans = 0;
        for (int i = 0, j = m - 1; i < m; ++i) {
            const auto &rcd = vr[i];
            // dbg(j, n, m - 1 - j, rcd[0], vl[j]);
            while (j >= 0 && n > m - 1 - j && rcd[0] < vl[j])
                acc += vl[j], --j;
            // dbg(rcd[0], i, vl[j], j, acc, ans);
            if (n == m - 1 - j)
                ans = max(ans, acc);
            if (n - m + j >= 0)
                if (rcd[1] > rcd[0])
                    ans = max(ans, acc + (n - m + j + 1) * rcd[0]);
                else
                    ans = max(ans, acc + rcd[1] + (n - m + j) * rcd[0]);
        }
        cout << ans << endl;
    }
    return 0;
};