#include <iostream> using namespace std; int dp[11000][11000], w[11000], c[11000]; int main(){ int x, n; cin >> x >> n; for(int i = 1; i <= n; i++){ cin >> c[i] >> w[i]; } for(int i = 1; i <= n; i++){ for(int j = c[i]; j <= x; j++){ dp[i][j] = max(dp[i - 1][j], dp[i][j - c[i]] + w[i]); } } cout << dp[n][x]; }