#include<iostream> #include<algorithm> using namespace std; int dp[20100]; int main(){ int v,n,wi,ci; cin>>v>>n; for(int i = 1; i <= n; i++){ cin>>wi>>ci; for(int j = v; j >= wi; j--){ dp[j] = max(dp[j],dp[j-wi]+ci); } } cout<<dp[v]; return 0; }