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