#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

// 可以支配的钱数、清单上可选择的物品种类、输入物品的价格、输入物品的受欢迎程度、状态转移表
int M, N, v[1005], p[1005], dp[1005][105] = {0};

int main() {
	while (~scanf("%d%d", &M, &N)) {
		vector<int> buy[105];  // 每个受欢迎程度下所购买的物品列表
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= N; ++i) scanf("%d%d", &v[i], &p[i]);
		// dp[i,j]代表前 i 个物品价格最大为 j 最高的受欢迎程度
		// buy[j]代表在价格 j 下且受欢迎程度最大时所购买的物品列表
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j <= M; ++j) {
				if (j - v[i] >= 0) {
					// 当加上物品 i 比不加物品 i 的受欢迎程度大
					if ((dp[i-1][j-v[i]] + p[i]) > dp[i-1][j]) {
						buy[j] = buy[j-v[i]];  // 先等于不加物品 i 且受欢迎程度最大的物品列表
						buy[j].push_back(i);  // 接着再把物品 i 追加上去
						dp[i][j] = dp[i-1][j-v[i]] + p[i];
					} else dp[i][j] = dp[i-1][j];
				}
				else dp[i][j] = dp[i-1][j];
			}
		}
		printf("%d\n", dp[N][M]);
		if (dp[N][M] != 0) {
			for (int i = 0; i < buy[...