#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[maxn][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 = 1 ; j <= m ; j++ )
        {
            if ( j < w[i] )  
            {
                f[i][j] = f[i-1][j];
            }
            else
            {
                if ( f[i-1][j] > f[i][ j - w[i] ] + c[i])  
                {
                    f[i][j] = f[i-1][j];
                }
                else 
                {
                    f[i][j] = f[i][ j - w[i] ] + c[i];
                } 
            }
        }
    }
    cout << "max=" << f[n][m];        
    return 0;
}