#include<iostream> using namespace std; int w[100005] , c[100005]; int dp[100005]; int main(){ int m , n; cin >> m >> n; for(int i = 1;i <= n;i++){ cin >> c[i] >> w[i]; } for(int i = 1;i <= n;i++){ for(int j = 0;j <= m;j++){ if(j >= w[i]) dp[j]=max(dp[j] , dp[j-w[i]] + c[i]); } } cout << dp[m]; return 0; }

#include<bits/stdc++.h> using namespace std; const int M=10001,N=10001; int m,n,w[N],c[N],f[M]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&w[i]); for(int i=1;i<=n;i++) for(int v=w[i];v<=m;v++) f[v]=max(f[v],f[v-w[i]]+c[i]); printf("%d\n",f[m]); }