#include<bits/stdc++.h> using namespace std; int main(){ int m,n,w[114514] = {0},i,j,c[114514],f[114514]; cin>>m>>n; for(i = 1;i <= n;i++){ cin>>w[i]>>c[i]; } for(i = 1;i <= n;i++){ for(int v = m;v >= w[i];v--){ if(f[v - w[i]] + c[i] > f[v]){ f[v] = f[v - w[i]] + c[i]; } } } cout<<f[m]<<endl; }