#include<bits/stdc++.h> using namespace std; long long d[230010],v[230010],w[230010],n,t; int main(){ cin>>t>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]; } for(int i=1;i<=n;i++){ for(int j=t;j>=w[i];j--){ d[j]=max(d[j],d[j-w[i]]+v[i]); } } cout<<d[t]; return 0; }