#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("be.in");
struct munka {
    int nap;
    int x;
    int y;
    int index;
};
bool comp2(munka a, munka b) {
    return a.x < b.x;
}
bool comp(munka a, munka b) {
    return a.nap < b.nap;
}
vector <munka> sdt;
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;

}
stack <munkaba> st;
vector <int> seg2;
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++) {
        int maxx = 0;
        int index1= 0;
        if (i>=3&&t[i-1].nap!=t[i-2].nap&& t[i-1].nap < t[i].nap) {  
            for (int j = i - 1; j >= 1 && j >= i - 2; j--) {
                //cout << j << ' ';   
                if (t[j].y != t[i].nap && t[j].nap != t[i].nap) {
                    if (hossz[j] + hossz[i] > maxx) {
                        munkaba  a;
                        a.hossz = hossz[i] + hossz[j];
                        maxx = a.hossz;
                        index1 = j;
                        a.os = j;
                        seg.push_back(a);
                    }
                }
                else {
                    if (t[os[j]].y != t[i].nap && t[os[j]].nap != t[i].nap) {
                        if (hossz[os[j]] + hossz[i] > maxx) {
                            munkaba  a;
                            a.hossz = hossz[i] + hossz[os[j]];
                            a.os = os[j];
                            maxx = a.hossz;
                            index1 = os[j];
                            seg.push_back(a);
                        }
                    }
                }
                
            }
        }
        else {
            for (int j = i - 1; j >= 1; j--) {
                if (maxx < hossz[j]+hossz[i]) {
                    if (t[j].y != t[i].nap && t[j].nap != t[i].nap) {
                        munkaba  a;
                        index1 = j;
                        a.hossz = hossz[i] + hossz[j];
                        maxx = a.hossz;
                        a.os = j;
                        seg.push_back(a);
                    }
                }
            }
        }
        if (maxx) {
            os[i] = index1;
            hossz[i] = maxx;
        }
    }

}
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 db6 = 0;
void munka2() {
    sort(t.begin(), t.end(), comp2);
    sdt.push_back(t.back());
    /*for (int i = 1; i <= n; i++) {
        cout << t[i].x << ' ' << t[i].index<<endl;
    }*/
    /*cout << endl;*/
    db6 += t.back().x;
    for (int i = t.size() - 2; i >= 1; i--) {
        bool d=1;
        for (int j = 0; j < sdt.size(); j++) {
            if (!(t[sdt[j].index].nap!=t[i].nap&&t[sdt[j].index].nap!=t[i].y&& t[sdt[j].index].y != t[i].nap)) {
                d = false;
            }
        }
        if (d) {
            sdt.push_back(t[i]);
            db6 += t[i].x;
        }
    }

}
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;
    //    }
    //}
    ////cout << endl << endl << endl;
    //visszalepesszamolas(index);
    //cout << maxx << ' ' << k << endl;
    //cout << t[index].index << ' ';
    //visszalepes(index);
    munka2();
    cout << db6 << ' ' << sdt.size() << endl;
    for (int i = 0; i < sdt.size(); i++) {
        cout << sdt[i].index << ' ';
    }


}