#include <bits/stdc++.h> using namespace std; int w[55], v[55]; int dp[55][605]; int main(){ int t, m; cin >> t >> m; for(int i = 1; i <= m; i++){ cin >> w[i] >> v[i]; } for(int i = 1; i <= m; i++){ for(int j = 1; j <= t; j++){ if(j >= w[i]){ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); }else{ dp[i][j] = dp[i - 1][j]; } } } cout << dp[m][t]; return 0; }