60PTS

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,n,w[1000001],v[1000001];
int f[10001][10001];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++) f[0][i]=0;
	for(int i=1;i<=n;i++) f[i][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j<w[i]) f[i][j]=f[i-1][j];
			else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
		}
	}
	cout<<f[n][m]<<endl;
}