...

#include<iostream>
using namespace std;
int w[100005] , c[100005];
int dp[100005];
int main(){
int m , n;
cin >> m >> n;
for(int i = 1;i <= n;i++){
cin >> c[i] >> w[i];
}
for(int i = 1;i <= n;i++){
for(int j = 0;j <= m;j++){
if(j >= w[i]) dp[j]=max(dp[j] , dp[j-w[i]] + c[i]);
}
}
cout << dp[m];
return 0;
}