#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int a[5001],v[10001],i,g,gprim,vmax[10001][10001],n,gmax;
int main()
{
    fin>>n>>gmax;
    for(i=1; i<=n; i++)
        fin>>a[i]>>v[i];
    for(i=1; i<=n; i++)
        for(g=1; g<=gmax; g++)
        {
            vmax[i][g]=vmax[i-1][g];
            if(a[i]<=g && v[i]+vmax[i-1][g-a[i]]>vmax[i-1][g])
                vmax[i][g]=v[i]+vmax[i-1][g-a[i]];
        }

    fout<<vmax[n][gmax];
}