zad_daa

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <queue>

int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v;
    for (int i = 0; i < m; i++)
    {
        int s, l;
        cin >> s >> l;
        v.push_back(pair<int, int>(s, l));
    }

    sort(v.begin(), v.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
        if (p1.first == p2.first)
            return p1.second > p2.second;
        return p1.first < p2.first;
        });

    priority_queue<int, vector<int>, std::greater<int>> studios;
    for (int i = 1; i <= n; i++)
        studios.push(i);

    priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, std::greater<pair<pair<int, int>, int>>> pq;
    for (int i = 0; i < m; i++)
    {
        int currArr = v[i].first;

        while (!pq.empty() && pq.top().first.first <= currArr)
        {
            auto p = pq.top();
            studios.push(p.second);
            pq.pop();
        }
        if (studios.empty() && !pq.empty())
        {
            auto curr = pq.top();
            pq.pop();
            pq.push({ {curr.first.first + v[i].second, curr.first.second}, curr.first.first });
        }
        else {
            pq.push({ {v[i].second + v[i].first, studios.top()}, v[i].first });
            studios.pop();
        }
    }
    pair<pair<int, int>, int> p;
    while (!pq.empty())
    {
        p = pq.top();
        pq.pop();
    }

    cout << p.first.first << " " << p.first.second;
}