#include <bits/stdc++.h>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int n,w[5001],p[5001],g,sol,dp[10001];

void read()
{
    in>>n>>g;
    for(int i=1;i<=n;++i)
        in>>w[i]>>p[i];
}

void solve()
{
    for(int i=1;i<=n;++i)
        for(int j=g-w[i];j>=0;--j)
            if(dp[j+w[i]]<dp[j]+p[i])
            {
                dp[j+w[i]]=dp[j]+p[i];
                if(dp[j+w[i]]>sol)
                    sol=dp[j+w[i]];
            }
}

void print()
{
    out<<sol;
}

int main()
{
    read();
    solve();
    print();
    return 0;
}