#include<bits/stdc++.h>
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;
}