#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream fin("be.in");
struct munka {
    int nap;
    int x;
    int y;
    int index;
};
bool comp (munka a, munka b){
    return a.nap < b.nap;
}
vector <munka> t;
int n, m;
void be() {
    cin >> m >> n;
    t.resize(n+1);
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        t[i].nap = a;
        t[i].x=b;
        t[i].y = a+1;
        t[i].index = i;
    }
    sort(t.begin(), t.end(),comp);
}
void ki() {
    cout << endl << endl << endl << endl << endl;
    for (int i = 1; i <= n; i++) {
        cout << t[i].nap << ' ' << t[i].x << endl;
    }
    cout << endl << endl << endl << endl << endl;
}
struct munkaba {
    int os;
    int hossz;
};
bool compare(munkaba a, munkaba b) {
    return a.hossz < b.hossz;
}
vector <munkaba> seg;
vector <int> os;
vector <int> hossz;
void munka() {
    hossz.resize(n + 1);
    os.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        hossz[i]=t[i].x;
        //cout << hossz[i] << ' '<<endl;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i-1; j >= i-4&&j>=1; j--) {
            if (t[j].y != t[i].nap && t[j].nap != t[i].nap) {
                munkaba  a;
                a.hossz = hossz[i] + hossz[j];
                a.os = j;
                seg.push_back(a);
            }
        }
        if (!seg.empty()) {
            sort(seg.begin(), seg.end(), compare);
            os[i] = seg.back().os;
            hossz[i] = seg.back().hossz;
            seg.clear();
        }
    }

}
int k = 1;
void visszalepesszamolas(int kcs) {
    if (os[kcs]) {
        k++;
        visszalepesszamolas(os[kcs]);
    }
}
void visszalepes(int kcs) {
    if (os[kcs]) {
        cout << t[os[kcs]].index << ' ';
        visszalepes(os[kcs]);
    }
}
int main()
{
    be();
    //ki();
    munka();
    //cout << endl << endl << endl;
    int maxx = hossz[1];
    int index = 1;
    for (int i = 1; i <= n; i++) {
        cout << hossz[i] << ' ';
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        if (maxx < hossz[i]) {
            maxx = hossz[i];
            index = i;
        }
    }
    visszalepesszamolas(index);
    cout << maxx<<' '<<k << endl;
    cout << t[index].index << ' ';
    visszalepes(index);
}