#include<bits/stdc++.h> using namespace std; int m,n,s[10001],t[10001],dp[10001]; int main(){ scanf("%d %d",&m,&n); for(int i=1;i<=n;i++) scanf("%d %d",&s[i],&t[i]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j>=t[i]) dp[j]=max(dp[j],dp[j-t[i]]+s[i]); } } printf("%d",dp[m]); return 0; }