#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;

ll inf = 1e18;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int w, n;
    cin >> w >> n;
    vector<pair<int,int>> a;
    for(int i = 0; i < n; i++)
    {
        int c1, w1;
        cin >> w1 >> c1;
        a.push_back({w1,c1});
    }
    vector<int> dp(251);
    dp[0] = 0;
    for(int i = 1; i < w+1; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i >= a[j].first)
            {
                dp[i] = max(dp[i], a[j].second + dp[i - a[j].first] );
            }
        }
    }
    cout << dp[w];
    return 0;
}