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

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        if (args.length > 0 && args[0].equals("LOCAL")) {
            in = new Scanner(new File("data/in.txt"));
            System.setOut(new PrintStream(new FileOutputStream("data/out.txt")));
        }

        int c = in.nextInt(), n = in.nextInt(); // c -- максимальная вместимость рюкзака, n -- количество предметов

        int[] weight = new int[n + 1]; // вес предмета
        int[] cost = new int[n + 1]; // стоимость предмета

        int[][] dp = new int[n + 1][c + 1]; // dp[i][j] -- максимальная стоимость, которую можно набрать, если взять первые i предметов и вместимость рюкзака равна j

        for (int i = 1; i <= n; i++) {
            weight[i] = in.nextInt();
            cost[i] = in.nextInt();
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= c; j++)
                if (j >= weight[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]]);
                else
                    dp[i][j] = dp[i - 1][j];

        System.out.println(dp[n][c]);



        in.close();
    }
}