#include <cstdio> #include <iostream> using namespace std; int T, M; int dp[1001]; int t[1001]; int v[1001]; int main() { scanf("%d %d",&T,&M); for (int i = 1; i <= M; i++) scanf("%d %d",&t[i],&v[i]); for (int i = 0; i <= T; i++) { if (i - t[1] >= 0) dp[i] = v[1]; else dp[i] = 0; } for (int i = 2; i <= M; i++) for (int k = T; k >= 1; k--) { if (k - t[i] >= 0 && dp[k] < dp[k - t[i]] + v[i]) dp[k] = dp[k - t[i]] + v[i]; } printf("%d\n",dp[T]); return 0; }