#include<fstream>
#include<climits>
using namespace std;

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

int dp[10002];

struct obiect
{
    int weight,value;
} v[5001];

int main()
{
    int n,gr,i,j,maxi=INT_MIN;
    f>>n>>gr;
    for(i=1; i<=n; i++)
        f>>v[i].weight>>v[i].value;
    for(j=0; j<=gr; j++)
        dp[j]=INT_MIN;
    dp[v[1].weight]=v[1].value;
    for(i=2; i<=n; i++)
    {
        for(j=gr-v[i].weight; j>=0; j--)
        {
            dp[j+v[i].weight]=max(dp[j+v[i].weight],dp[j]+v[i].value);
            if(dp[j+v[i].weight]>maxi)
                maxi=dp[j+v[i].weight];
        }
    }
    g<<maxi;
    return 0;
}