package Lab3;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

class PbRucsacului {

	private int n;
	private int Gtot;
	private int[] G;
	private int[] P;
	private int[] D = {0};
	
	public PbRucsacului(int n, int gtot, int[] g, int[] p) {
		super();
		this.n = n;
		Gtot = gtot;
		G = g;
		P = p;
		D = new int[2 * n + 1];
	}
	
	public int RezolvarePD() {
		
		for(int i = 1; i <= n; i++){
			for(int j = Gtot - G[i]; j >= 0; j--){
				if(D[j + G[i]] <= D[j] + P[i])
					D[j + G[i]] = D[j] + P[i];
			}
		}
		
		return D[Gtot];
	}

	public static void main(String[] args) {
		
		int n, g;
	
		try{
			Scanner sc = new Scanner(new File("rucsac.in"));
			
			g = sc.nextInt();
			n = sc.nextInt();
			int[] w = new int[n + 1];
			int[] p = new int[n + 1];
			
			for(int i = 1; i <= n; i++){
				w[i] = sc.nextInt();
				p[i] = sc.nextInt();
			}
			
			
			PbRucsacului pb = new PbRucsacului(n,g,w,p);
			PrintWriter printer = new PrintWriter(new File("rucsac.out"));
			printer.print(pb.RezolvarePD());
			
			sc.close();
		}
		catch(FileNotFoundException e) {
			System.out.println("Err");
		}
		
	}

}