#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int gg,n,g[5005],v[5005],sum[10010];
int main()
{
    cin>>n>>gg;
    for(int i=1;i<=n;i++)
        cin>>g[i]>>v[i];
    sum[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=gg-g[i];j>=0;j--)
        {
             if(sum[j+g[i]]<sum[j]+v[i])
                sum[j+g[i]]=sum[j]+v[i];
        }
    cout<<sum[gg];
    cin.close();
    cout.close();
    return 0;
}