#include <bits/stdc++.h>
using namespace std;

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

int n,g,maxim;
int v[5005], gr[5005],dp[5][10005];

int main()
{
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>gr[i]>>v[i];
    int aux=1;
    for(int i=1; i<=n; i++)
    {
        if(aux==0)
            aux=1;
        else
            aux=0;
        for(int j=0; j<=g; j++)
        {
            dp[aux][j]=dp[1-aux][j];
            if(j>=gr[i])
                dp[aux][j]=max(dp[1-aux][j-gr[i]]+v[i], dp[aux][j]);
        }
    }
    for(int i=0; i<=g; i++)
        maxim=max(maxim, dp[aux][i]);
    fout<<maxim;
    return 0;
}