#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN],w[MAXN],f[MAXN][MAXN];
int main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;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;
}