1. #include <bits/stdc++.h>

using namespace std;
const int N = 201;
int mem[N][N];
int v[N], w[N];
int n, m;//n是物品，m是重量
int dfs(int x, int spv) {
if(mem[x][spv])return mem[x][spv];
int sum=0;
if(x>n)return sum =0;
if(spv<v[x])sum=dfs(x+1,spv);
else if(spv>=v[x]){
sum=max(dfs(x+1,spv),dfs(x+1,spv-v[x])+w[x]);
}
mem[x][spv]=sum;
return sum;
}
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
memset(mem, 0, sizeof mem);
int ans = dfs(1, m);
cout << ans;
return 0;
}