#include<bits/stdc++.h> using namespace std; int times,number; int timess[1001],scores[1001]; int backpack_dp[1001][1001]; int main() { cin>>times>>number; for(int i=1;i<=number;i++) {cin>>timess[i]>>scores[i];} for(int i=1;i<=number;i++){ for(int j=times;j>=1;j--) {if(timess[i]<=j) {backpack_dp[i][j]=max(backpack_dp[i-1][j],backpack_dp[i-1][j-timess[i]]+scores[i]);} else {backpack_dp[i][j]=backpack_dp[i-1][j];}}} cout<<backpack_dp[number][times]; }