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