#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int c, n;  // c 额度 n 点菜数目
    scanf("%d%d", &c, &n);
    int p[101];  // 价值
    int v[101];  // 评分
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i], &v[i]);
    }
    int dp[1001][102]; // 考虑0-101 一共102个

    // dp[x][y] 在总额度不超过x块情况，考察0->y-1号商品的最大评分
    for (int y = 0; y <= n; y++) {
        dp[0][y] = 0;  // 没钱,评分为0
    }
    for (int x = 0; x <= c; x++) {
        dp[x][0] = 0;  // 没商品，评分为0
    }

    for (int x = 1; x <= c; x++) {
        for (int y = 1; y <= n; y++) {
            if (x - p[y - 1] < 0) {  // 没钱，买不起后面的商品
                dp[x][y] = dp[x][y - 1];
            }
            else {
                dp[x][y] = max(dp[x][y - 1], dp[x - p[y - 1]][y - 1] + v[y - 1]);
            }
        }
    }
    printf("%d\n",dp[c][n]);
    return 0;
}