import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();
        int n = scanner.nextInt();
        int[] price = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            price[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }
        System.out.println(maxValue(money, n, price, value));
    }

    private static int maxValue(int money, int n, int[] price, int[] value) {
        int[][] dp = new int[n + 1][money + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= money; j++) {
                if (price[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price[i - 1]] + value[i - 1]);
                }
            }
        return dp[n][money];
    }
}

package com;


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static List<String> res = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    static boolean[] used;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] str = s.substring(1, s.length() - 1).split(",");
        int[] a = new int[str.length];
        used = new boolean[a.length];
        for (int i = 0; i < a.length; i++)
            a[i] = Integer.parseInt(str[i]);
        System.out.print(reletive_7(a));
    }

    public static int reletive_7(int[] digit) {
        pailie(digit, sb, used);
        int count = 0;
        int[] a = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            a[i] = Integer.parseInt(res.get(i));
            if (a[i] % 7 == 0)
                count++;
        }
        return count;
    }

    private static void pailie(int[] num, StringBuilder sb, boolean[] used) {
        if (sb.length() == num.length) {
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (used[i])
                continue;
            used[i] = true;
            sb.append(String.valueOf(num[i]));
            pailie(num, sb, used);
            used[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}