#include <stdio.h> #include <string.h> int w[20000],p[200000]; int dp[20000]; int main() { int n,m,i,j,k; scanf("%d %d", &m,&n); for(i=1; i<=n; i++) scanf("%d %d", &w[i],&p[i]); for(i=1; i<=n; i++) for(k=p[i]; k<=m; k++) dp[k]=dp[k]>dp[k-p[i]]+w[i]?dp[k]:dp[k-p[i]]+w[i]; printf("%d", dp[m]); return 0; }