import java.io.*;
import java.util.*;

public class Question4
{
	public static void main(String[]args)throws IOException
	{
		Scanner in = new Scanner(new FileReader("DATA4.txt"));
		PrintWriter out = new PrintWriter(new FileWriter("OUT4.txt"));
		
		while(in.hasNext())
		{
			int space = in.nextInt();
			int num = in.nextInt();
			int[][] albums = new int[num][2];
			int utility = 0;			
			
			for(int i = 0; i<albums.length;i++)
			{	for(int j=0; j<albums[i].length; j++)
				{
					albums[i][j] = in.nextInt();
					System.out.print(albums[i][j]);
				}
			System.out.println();}
			
			int max=0;
			while(space > 0)
			{	
				int maxu = 0;
			
				for(int i=0; i<albums.length; i++)
					if(albums[i][1] > maxu)
					{
						maxu = albums[i][1];
						max = i;
					}
				System.out.println(max);
				if(maxu == 0)
					space = 0;
				else if(albums[max][0] < space)
				{
					utility += albums[max][1];
					space -= albums[max][0];
				}
				albums[max][1] = 0;
				System.out.println(utility);
			}

			out.println(utility);
		}
		
		out.close();
	}
}