#include<bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    int a[1005]; //第i件物品的钱  下标从1开始
    int po[1005];//第i件物品的popularity
    vector<int> q[1005];
    int dp[1005][105];

    while(cin>>m>>n){  //m:前的总数  n：物品的总量
        for(int i=1;i<=n;i++){
            cin>>a[i]>>po[i];
        }
        dp[0][0]=0;
        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;++i){
            for(int j=0;j<=m;++j){
                if(j>=a[i] && dp[i-1][j-a[i]]+po[i]> dp[i-1][j]){
                    dp[i][j] = dp[i-1][j-a[i]]+po[i];
                    q[j]=q[j-a[i]];
                    q[j].push_back(i); 
                    //debug用的： cout<<i;              
                }
                else  dp[i][j]=dp[i-1][j];  
    /*debug: 刚刚写的是dp[i-1,j];   要会看error的提示
    1567Buyer.cpp:23:40: error: invalid conversion from 'int*' to 'int' [-fpermissive]
    else  dp[i][j]=dp[i-1,j];
    */
            }
        }

        cout<<dp[n][m]<<endl;
        if(dp[n][m]!=0){
            for (int i = 0; i < q[m].size(); i++){
					cout<<q[m][i]<<" "; }
		    cout<<endl;
        }
        

     /*  这个少了一个数 为啥子捏??
      while(!q[m].empty()){
            int now=q[m].front();
            cout<<now<<" ";
            q[m].pop_back();
        }
        cout<<endl;
    */
    }

    return 0;
}