#include <bits/stdc++.h>

using namespace std;

ifstream fin("pusculita.in");
ofstream fout("pusculita.out");

int s, n;
int greutate[101];
int cost[101];
array<int, 10001> dp1;/// dp[i] suma minima de greuate i
array<int, 10001> dp2;


int main() {

    fin>>s>>n;
    for(int i = 1; i <= n; i++){
        fin>>greutate[i];
        fin>>cost[i];
    }

    fill(dp2.begin(), dp2.end(), INT_MAX);
    dp2[0] = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= s; j++){
            if(greutate[i] > j)
                dp1[i] = dp2[i];
            else
                dp1[i] = max(dp2[i], dp2[i] + greutate[i]);
        }
        dp2 = dp1;
    }

    fout<<dp2[s];

    return 0;
}