#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 35, M = 205;
int m, n, v[N], w[N], dp[N][M], ans[N], t; // dp[i][j] 前i个物品在j的背包容量下价值最大值
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	// 使用二维数组DP 便于输出路径
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (v[i] > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	int res = dp[n][m];
	// 输出路径
	while (n && m)
	{
		if (dp[n][m] == dp[n - 1][m - v[n]] + w[n]) // 判断是否选择了当前物品
			ans[++t] = n, m -= v[n];				// 记录路径 更新当前总价值
		n--;
	}
	cout << res << endl
		 << t << endl;
	for (int i = t; i >= 1; i--)
		cout << ans[i] << " ";
}