#include <fstream>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");

int n,g,v[10005],cost[5005],val[5005],maxi;

int main()
{
    int i,j;
    in>>n>>g;
    for(i=1;i<=n;i++)
        in>>cost[i]>>val[i];
    v[0]=1;
    for(i=1;i<=n;i++)
        for(j=g;j>=0;j--)
            if(v[j]!=0 and j+cost[i]<=g)
                v[j+cost[i]]=max(v[j+cost[i]],v[j]+val[i]);
    for(i=1;i<=g;i++)
        if(maxi<v[i])
            maxi=v[i];
    out<<maxi-1;
    return 0;
}