#include <bits/stdc++.h> using namespace std; int t, m, dp[1010], w[110], v[110]; int main(){ ios::sync_with_stdio(false); 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 = t; j >= w[i]; j--) dp[j] = max(dp[j - w[i]] + v[i], dp[j]); } cout << dp[t]; return 0; }