#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N];
int w[N],v[N];//体积 价值
int n,c;//数量 体积
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=c;j>=0;j--)
{
g[j]=g[j];
if(j>=w[i])
{
g[j]=max(g[j],g[j-w[i]]+v[i]);
}
}
}
cout<<g[c]<<endl;
return 0;
}