dp

#include<bits/stdc++.h>
using namespace std;
int main(){
int C,N;
cin>>C>>N;
int w[100005],v[100005],dp[1005][1005];
for(int i=1;i<=C;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=N;i++){
for(int j=0;j<=C;j++){
if(j<w[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout<<dp[N][C];
return 0;
}