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

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

int n,g,d[5005],m,v;

int main()
{
    fin>>n>>g;
    for(int i=1; i<=5004; i++) d[i]=-1;

    for(int i=0; i<n; i++)
    {
        fin>>m>>v;
        for(int i=g; i>=0; i--)
        {
            if(d[i]!=-1)
            {
                d[i+m]=max(d[i+m], d[i]+v);
            }
        }
    }
    int val=0;
    for(int i=g; i>=0; i--)
    {
        if(d[i]>val) val=d[i];
    }
    fout<<val;
}