import java.util.Scanner;
class Main {
    static int time;
    static int number;
    static int[] cost = new int[105];
    static int[] value = new int[105];
    static int[][] dp = new int[105][1005];
    public static void main(String argus[]) {
        Scanner sc = new Scanner(System.in);
        time = sc.nextInt();
        number = sc.nextInt();
        for (int i = 1; i <= number; i++) {
            cost[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        for (int i = 0; i <= number; i++) {
            dp[number][0] = 0;
        }
        for (int i = 0; i <= time; i++) {
            dp[0][time] = 0;
        }
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= time; j++) {
                if (j >= cost[i]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);
                }
            }
        }
        System.out.println(dp[number][time]);
    }
}