#include<iostream>
#include<vector>
using namespace std;
int main() {
	int M, N;
	while (cin >> M >> N) {
		int dp[101] = {0}, w, v;
		vector<int> path[1001];//动态更新路径
		for (int i = 1; i <= N; i++) {
			cin >> w >> v;
			for (int j = M; j >= w; j--)
				if (dp[j - w] + v > dp[j]) {
					dp[j] = dp[j - w] + v;
					path[j] = path[j - w];
					path[j].push_back(i);
				}
		}
		cout << dp[M] << endl;
		if(dp[M]) {
			for(int i = 0; i < path[M].size(); i++)
				cout << path[M][i] << ' ';
			cout << endl;
		}
	}
}