#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

struct Munka{
    int nap;
    int bevetel;
    int index;
};

int n, m;
int utolso;
vector<Munka> munkak;
vector<long long> maxBevetel;
vector<int> munkaIndex;
vector<int> elozoNap;

void Beolvas(){
    cin>>n>>m;
    munkak.resize(m+1);
    maxBevetel.resize(n+1, 0);
    munkaIndex.resize(n+1, 0);
    elozoNap.resize(n+1, 0);
    for(int i = 1; i <= m; i++){
        cin>>munkak[i].nap>>munkak[i].bevetel;
        munkak[i].index = i;
    }
}

bool Comapre(Munka a, Munka b){
    return a.nap < b.nap;
}

int LegnagyobbAznap(int startIndex, int nap){
    int i = startIndex;
    int maxIndex = startIndex;
    while(munkak[i].nap <= nap){
        if(munkak[maxIndex].bevetel < munkak[i].bevetel)maxIndex = i;
        i++;
    }
    return maxIndex;
}

int Elso(){
    if(munkak[1].nap != 1)return 1;
    int indMax = LegnagyobbAznap(1,1);
    maxBevetel[1] = munkak[indMax].bevetel;
    munkaIndex[1] = munkak[indMax].index;
    utolso = 1;
    return indMax;
}

void Feladat(){
    sort(munkak.begin()+1, munkak.end(), Comapre);
    int elozoIndex = Elso();
    for(int i = 2; i <= n && elozoIndex < m; i++){
        int indexMax = LegnagyobbAznap(elozoIndex+1, i);
        if(indexMax){
            munkaIndex[i] = munkak[indexMax].index;
            maxBevetel[i] = munkak[indexMax].bevetel;
            for(int j = 1; j < i-1; j++){
                if(maxBevetel[j] + munkak[indexMax].bevetel > maxBevetel[i]){
                    maxBevetel[i] = maxBevetel[j] + munkak[indexMax].bevetel;
                    elozoNap[i] = j;
                }
            }
            elozoIndex = indexMax;
            if(maxBevetel[i] > maxBevetel[utolso])utolso = i;
        }
    }
}

void Kiir(){
    stack<int> napIndex;
    napIndex.push(utolso);
    cout<<maxBevetel[utolso]<<' ';
    while(elozoNap[napIndex.top()]){
        napIndex.push(elozoNap[napIndex.top()]);
    }
    cout<<napIndex.size()<<'\n';
    while(!napIndex.empty()){
        cout<<munkaIndex[napIndex.top()]<<' ';
        napIndex.pop();
    }
}

int main(){
    Beolvas();
    Feladat();
    Kiir();
    return 0;
}