#include<iostream>
#include<cstdio>
using namespace std;
const int N = 35;
int n, m, w[N], c[N];
int mx;
int f[N][1005];
void dfs(int step, int left,int sum)// 1 - n
{
if(step > n)
{
mx = max(mx, sum);
return;
}
dfs(step + 1, left, sum);
if(left >= w[step])
{
dfs(step + 1, left - w[step], sum + c[step]);
}

}
int dfs2(int i, int j)
{
if(j <= 0) return 0;
if(i < 1) return 0;
if(f[i][j]) return f[i][j];
int ans = 0;
// no selected
ans = max(ans, dfs2(i - 1, j));
// selected
if(j >= w[i])
ans = max(ans, dfs2(i - 1, j - w[i]) + c[i]);
return f[i][j] = ans;
}
int main(void)
{
ios::sync_with_stdio(0);
cin >> m >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> c[i];
}
//dfs(1, m, 0);
//cout << mx << endl;
cout << dfs2(n, m) << endl;
return 0;
}