#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t, m; cin >> t >> m; vector<int> w(m + 1), c(m + 1); vector<int> dp(t + 1, 0); for(int i = 1; i <= m; i++){ cin >> w[i] >> c[i]; } for(int i = 1; i <= m; i++){ for(int j = t; j >= w[i]; j--){ dp[j] = max(dp[j], dp[j - w[i]] + c[i]); } } cout << dp[t]; return 0; }