#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("graf.txt");

struct munka{
    int nap;
    int ar;
    int sorszam;
};

int n,m;
vector<munka> M;
vector<int> Osszeg;
vector<int> Osvektor;
stack<int> Indexek;

void beolvas(){
    f>>n>>m;
    M.resize(n+1);
    for(int i=1;i<=m;i++){
        munka m1;
        f>>m1.nap>>m1.ar;
        m1.sorszam=i;
        if(M[m1.nap].ar<m1.ar){
            M[m1.nap]=m1;
        }
    }
}

void kiir_M(){
    for(int i=1;i<=n;i++){
        cout<<M[i].nap<<' '<<M[i].ar<<' '<<M[i].sorszam<<'\n';
    }
}

void munkaa(){
    Osszeg.resize(n+1);
    Osvektor.resize(n+1);
    for(int i=1;i<=n;i++){
        if(i<=2){
            Osszeg[i]=M[i].ar;
            Osvektor[i]=0;
        }
        else{
            munka maxi_munka;
            maxi_munka.ar=0;
            for(int j=1;j<i-1;j++){
                if(M[j].ar>=maxi_munka.ar){
                    maxi_munka=M[j];
                }
            }
            Osvektor[i]=maxi_munka.sorszam;
            Osszeg[i]=Osszeg[maxi_munka.nap]+M[i].ar;
            //cout<<'\n'<<maxi_munka.nap<<' '<<maxi_munka.ar<<' '<<maxi_munka.sorszam;
        }
    }
    int maxi=0,kindex;
    munka maxi_munka2;
    maxi_munka2.ar=0;
    for(int i=1;i<=n;i++){
        if(Osszeg[i]>maxi){
            maxi=Osszeg[i];
            kindex=i;
        }
    }
    int drb=0;
    cout<<maxi;
    Indexek.push(kindex);
    int index=kindex;
    while(index){
        if(Osvektor[index]!=0)Indexek.push(Osvektor[index]);
        drb++;
        index=Osvektor[index];
    }
    cout<<' '<<drb;
    //cout<<'\n'<<maxi_munka2.nap<<' '<<maxi_munka2.ar<<' '<<maxi_munka2.sorszam<<'\n';
}

void stack_kiir(){
    cout<<'\n';
    while(!Indexek.empty()){
        cout<<Indexek.top()<<' ';
        Indexek.pop();
    }
}

void osszeg_kiir(){
    cout<<'\n';
    for(int i=1;i<=n;i++){
        cout<<Osszeg[i]<<' ';
    }
}

void os_kiir(){
    cout<<'\n';
    for(int i=1;i<=n;i++){
        cout<<Osvektor[i]<<' ';
    }
}

int main()
{
    beolvas();
    //kiir_M();
    munkaa();
    //osszeg_kiir();
    //os_kiir();
    stack_kiir();



    return 0;
}