#include <stdio.h>

#define maxP 100
#define maxN 100
#define MAX(a,b) (((a)>(b))?(a):(b))

int main() {
	int N;          // kolik zloděj unese
	int P;          // počet předmětů
	int m[maxP];    // hmotnosti předmětů
	float c[maxP];  // ceny předmětů

	// maximální hodnota lupu z prvních p předmětů v batohu s kapacitou n
	float batoh[maxP][maxN];

	scanf("%d %d", &N, &P);
	for (int i=1; i<=P; i++)
		scanf("%d %f", &m[i], &c[i]);

	for (int j=0; j<=N; j++)
		batoh[0][j] = 0;

	// postupně přidáváme předměty
	for (int i=1; i<=P; i++) {
		for (int j=0; j<m[i]; j++)  // nízké hmotnosti jenom zkopírujeme
			batoh[i][j] = batoh[i-1][j];
		for (int j=m[i]; j<=N; j++) // pokud lze, zlepšíme i-tým předmětem
			batoh[i][j] = MAX(batoh[i-1][j], batoh[i-1][j-m[i]]+c[i]);
	}

	printf("cena: %f\n", batoh[P][N]);
	printf("předměty:");
	for (int i=P, j=N; i>0; i--)
		if (batoh[i][j] > batoh[i-1][j]) { //předmět i je v batohu, vylepšil celkovou cenu
			printf(" %d", i);
			j -= m[i];
		}

	return 0;
}