#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int t, m; cin >> t >> m; vector<int> time(m + 1), value(m + 1); for (int i = 1; i <= m; ++i) { cin >> time[i] >> value[i]; } vector<vector<int>> dp(m + 1, vector<int>(t + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 0; j <= t; ++j) { dp[i][j] = dp[i - 1][j]; if (j >= time[i]) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]); } } } cout << dp[m][t] << endl; return 0; }