#include <iostream>

using namespace std;

struct Item {
    int weight, value;
};

constexpr int MAX_N = 105, MAX_CAPACITY = 1005;
int capacity, n;
Item items[MAX_N];
int dp[2][MAX_CAPACITY];
bool ping_pong;

void log_dp() {
    // for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= capacity; j++) {
            clog << dp[ping_pong][j] << "\t";
        }
        clog << endl;
    // }
}

void solve_dp() {
    // for (int i = 0; i <= capacity; i++) { dp[0][i] = 0; }
    // for (int i = 0; i <= n; i++) { dp[i][0] = 0; }
    for (int stop_item = 1; stop_item <= n; stop_item++, ping_pong = !ping_pong) {
        for (int w = 1; w <= capacity; w++) {
            dp[ping_pong][w] = dp[!ping_pong][w];
            if (w >= items[stop_item - 1].weight) { // 负数
                dp[ping_pong][w] =
                    max(dp[ping_pong][w],
                        dp[!ping_pong][w - items[stop_item - 1].weight] + items[stop_item - 1].value);
            }
        }
        // log_dp();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> capacity >> n;
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
    }

    solve_dp();
    cout << dp[!ping_pong][capacity] << endl;


    return 0;
}