//丹阳新区实小路彦

include[HTML_REMOVED]

using namespace std;

const int N = 1005;
int f[N][N], w[N], v[N];

int main()
{
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i)
cin >> w[i] >> v[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 f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
cout << f[n][m] << endl;
return 0;
}