#include <bits/stdc++.h>

using namespace std;

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

struct object
{
    int weight,value;
}a[5005];

long long dp[10005];
int N,G;

void read()
{
    fin>>N>>G;

    for(int i=1;i<=N;i++)
        fin>>a[i].weight>>a[i].value;
}

void best()
{
    long long sol=0;
    for(int i=1;i<=N;i++)
        for(int j=G-a[i].weight;j>=0;j--)
            if(dp[j+a[i].weight]<dp[j]+a[i].value)
            {
                dp[j+a[i].weight]=dp[j]+a[i].value;
                sol=max(sol,dp[j+a[i].weight]);
            }
    fout<<sol;
}

int main()
{
    read();
    best();
    return 0;
}