#include <iostream> #include <vector> using namespace std; int main() { int M, N; cin >> M >> N; vector<int> weight(N), value(N); for (int i = 0; i < N; i++) { cin >> weight[i] >> value[i]; } vector<int> dp(M + 1, 0); for (int i = 0; i < N; i++) { for (int j = weight[i]; j <= M; j++) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[M] << endl; return 0; }