#define ll long long
#define vec vector<int>
#define inf 0x3f3f3f3f
#define MAX 1005
#define P pair<int,int>
#define MOD 1000000

int main() {
	int n, m, w[MAX], v[MAX], dp[MAX];
	while (cin >> m >> n) {
		memset(dp, 0, sizeof(dp));
		vec ve[MAX];
		for (int i = 1; i <= n; i++)cin >> w[i] >> v[i];
		for (int i = 1; i <= n; i++) {
			for (int j = m; j >= w[i]; j--)
				if (dp[j - w[i]] + v[i] > dp[j]) {
					dp[j] = dp[j - w[i]] + v[i];
					ve[j] = ve[j - w[i]];
					ve[j].push_back(i);
				}
		}
		cout << dp[m] << endl;
		if (dp[m] != 0) {
			for (int i = 0; i < ve[m].size(); i++)
				cout << ve[m][i] << ' ';
			cout << endl;
		}
	}
}