#include<bits/stdc++.h> using namespace std; long long n, V, w[105], v[105], dp[105][100005]; int main (){ cin >> V >> n; for (int i = 1; i <= n; i++){ cin >> v[i] >> w[i]; } memset(dp, 0x8f, sizeof(dp)); dp[0][0] = 0; for (int i = 1; i <= n; i++){ for (int j = 0; j <= V; j++){ dp[i][j] = dp[i - 1][j]; if (j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); } } long long ans = 0; for (int i = 0; i <= V; i++){ ans = max(ans, dp[n][i]); } cout << ans << endl; return 0; }