#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> prev(n + 1, -1), val(n + 1, 0);

    for (int i=0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        if (v > val[u]) {
            val[u] = v;
        }
    }

    int idx = 0;
    if (val[0] > val[1]) {
        val[1] = val[0];
        prev[1] = 0;
    } else {
        idx = 1;
    }


    for (int i=2; i <= n; i++) {
        if (val[i - 1] > val[i - 2] + val[i]) {
            val[i] = val[i - 1];
            prev[i] = i - 1;
        } else {
            val[i] += val[i - 2];
            prev[i] = i - 2;
        }
        if (val[idx] < val[i]) {
            idx = i;
        }
    }

    cout << val[idx] << ' ';

    vector<int> ans(0);

    while (idx > 0) {
        if (prev[idx] != idx + 1) {
            ans.push_back(idx + 1);
        }
        idx = prev[idx];
    }

    cout << ans.size() << '\n';

    sort(ans.begin(), ans.end());

    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}