import java.io.*;
import java.util.*;
public class Knapsack {
	public static void main(String[] args) throws Exception {
		Scanner file = new Scanner(new File("knapsack.in"));
		int w = file.nextInt();
		int n = file.nextInt();
		int[] values = new int[n+1];
		int[] weights = new int[n+1];
		//1 based indexing
		for(int i = 1; i <= n; i++) {
			values[i] = file.nextInt();
			weights[i] = file.nextInt();
		}
		int[][] dp = new int[n+1][w+1];
		int[][] find = new int[n+1][w+1];
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j <= w; j++) {
				if(weights[i] > j) {
					dp[i][j] = dp[i-1][j];
					find[i][j] = 0;
				}
				else {
					if(dp[i-1][j] > dp[i-1][j-weights[i]]+values[i]) {
						dp[i][j] = dp[i-1][j];
						find[i][j] = 0;
					}
					else {
						dp[i][j] = dp[i-1][j-weights[i]]+values[i];
						find[i][j] = 1;
					}
				}
			}
		}
		System.out.println(dp[n][w]);
		int W = w;
		for(int i = n; i >= 1; i--) {
			if(find[i][W] == 1) {
				System.out.println(values[i] + " " + weights[i]);
				W -= weights[i];
			}
		}
	}
}