#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");ofstream fout("rucsac.out");
int v[1010],g[5010],val[5010],n,gmax;

int main()
{
    int i,j;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
    {
        fin>>g[i]>>val[i];
    }
    for(i=1;i<=gmax;i++)
    {
        if(g[1]<=i)
            v[i]=val[1];
    }
    for(i=2;i<=n;i++)
    {
        for(j=gmax;j>=1;j--)
        {
            if(j-g[i]>=0)
            {
                if(v[j-g[i]]+val[i]>v[j])
                    v[j]=v[j-g[i]]+val[i];
            }
        }
    }
    fout<<v[gmax];
}