import java.io.*;
import java.awt.*;
import java.lang.String;


public class q4
{

    public static void main (String[] args) throws IOException
    {
	BufferedReader input = new BufferedReader (new FileReader ("DATA4.txt"));
	PrintWriter output = new PrintWriter (new FileWriter ("OUT4.txt"));


	for (int c = 0 ; c < 5 ; c++)
	{

	    int space = Integer.parseInt (input.readLine ());
	    int num = Integer.parseInt (input.readLine ());

	    int size[] = new int [num];
	    int util[] = new int [num];

	    for (int i = 0 ; i < num ; i++)
	    {
		String s = input.readLine ();
		String[] sa = s.split (" ");

		size [i] = Integer.parseInt (sa [0]);
		util [i] = Integer.parseInt (sa [1]);
	    }

	    int limit = (int) Math.pow (2, num) - 1;
	    int best = 0;
	    for (int i = 0 ; i <= limit ; i++)
	    {

		String bin = Integer.toBinaryString (i);
		int len = bin.length ();
		int si = 0;
		int ut = 0;

		for (int b = 0 ; b < num ; b++)
		{
		    int temp = 0;
		    if (b < num - len)
		    {
			temp = 0;
		    }
		    else
		    {
			temp = Integer.parseInt ((bin.charAt (b - (num - len))) + "");
		    }
		    si += size [b] * temp;

		    if (si > space)
		    {
			ut = -3;
			break;

		    }
		    ut += util [b] * temp;
		}

		if (ut > best)
		    best = ut;
	    }

	    output.println (best);
	    input.readLine ();
	} //5 cases

	output.close ();
    } // main method
} // CC class