#include<bits/stdc++.h> using namespace std; int f[3][10005],v[10005],w[10005]; int main(){ int n,capa; cin>>capa>>n; for (int i = 1;i <= n;i++){ cin>>w[i]>>v[i]; } for (int i = 1;i <= n;i++){ for (int j = capa;j >= 0;j--){ if (j >= w[i]){ f[i & 1][j] = max(v[i] + f[(i - 1) & 1][j - w[i]],f[(i - 1) & 1][j]); } else{ f[i & 1][j] = f[(i - 1) & 1][j]; } } } cout<<f[n & 1][capa]<<endl; return 0; }