import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner inScanner=new Scanner(System.in);
		int n=inScanner.nextInt(),m=inScanner.nextInt();
		long[] a=new long[1010],b=new long[1010];
		long[][] s=new long[1010][1010];
		for (int i = 1; i <=m; i++) {
			a[i]=inScanner.nextInt();
			b[i]=inScanner.nextInt();
		}
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j <=n; j++) {
				for(int k = 0; k*a[i]<=j; k++) {
					if (j>=k*a[i]) {
						s[i][j]=Math.max(s[i-1][j], s[i-1][(int) (j-k*a[i])]+k*b[i]);
					}else {
						s[i][j]=s[i-1][j];
					}
				}
			}
		}
		System.out.println(s[m][n]);
	}
}