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