#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<Munka> legnagyobbMunka;
vector<long long> maxBevetel;
vector<int> elozoNap;

void Beolvas(){
    cin>>n>>m;
    munkak.resize(m+1);
    maxBevetel.resize(n+1, 0);
    elozoNap.resize(n+1, 0);
    legnagyobbMunka.resize(n+1, {0,0,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;
}

void Legnagyobbak(){
    sort(munkak.begin()+1, munkak.end(), Comapre);
    int j = 1;
    for(int i = 1; i <= n; i++){
        while(munkak[j].nap == i){
            if(legnagyobbMunka[i].bevetel < munkak[j].bevetel){
                legnagyobbMunka[i] = munkak[j];
            }
            j++;
        }
    }
}

void Feladat(){
    Legnagyobbak();
    maxBevetel[1] = legnagyobbMunka[1].bevetel;
    for(int i = 2; i <= n; i++){
        if(legnagyobbMunka[i].index){
            maxBevetel[i] = legnagyobbMunka[i].bevetel;
            for(int j = 1; j < i-1; j++){
                if(maxBevetel[j] + legnagyobbMunka[i].bevetel > maxBevetel[i]){
                    maxBevetel[i] = maxBevetel[j] + legnagyobbMunka[i].bevetel;
                    elozoNap[i] = j;
                }
            }
            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<<legnagyobbMunka[napIndex.top()].index<<' ';
        napIndex.pop();
    }
}

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