#include <bits/stdc++.h>
using namespace std;
const int maxm = 200 + 5, maxn = 30 + 5;
int m, n;
int w[maxn], c[maxn];
int f[maxm]; 
int main()
{
    cin >> m>> n;           
    for ( int i = 1 ; i <= n ; i++ )
    {
        cin >> w[i] >> c[i];
    }     
    for ( int i = 1 ; i <= n ; i++)             
    {
        for ( int j = m ; j >= w[i] ; j-- )
        {
            if ( f [ j - w[i] ] + c[i] > f[j] )
            {
                f[j] = f [ j - w[i] ] + c[i];
            }
        }
    }
    cout << f[m];                      
    return 0;
}