#include<bits\stdc++.h>
using namespace std;
int w[2000],v[2000],f[2000];
int k[2000][2000];
int main(){
	int n,m;
	cin>>m>>n;
	for(int i = 0; i < n;i++)
		cin>>w[i]>>v[i];
	for(int i=0;i<n;i++)
	    for(int c=m;c>=1;c--)
	        if(c>=w[i]){
				if(f[c] < f[c-w[i]]+v[i]) k[i][c] = 1;
				else k[i][c] = 0;
	       		f[c]=max(f[c],f[c-w[i]]+v[i]);
	       	}
	cout<<f[m]<<endl<<"取序号\n";
	for(int i = n - 1; i >= 0; i--)
		if(k[i][m]){
			cout<<i + 1<<endl;
			m-=w[i];
		}
	return 0;
}