#include<iostream>
#include<fstream>
#include<vector>
#define N_MAX 10001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g;
vector< int > vec;
vector< int > vec2;
void print_vec(vector< int > v)
{
    for(int i=0;i<v.size();i++)
    {
        fout<<v[i]<<" ";
    }
    fout<<"\n";
}
int main()
{
    fin>>n>>g;
    int w,p;
    fin>>w>>p;
    for(int i=0;i<=g;i++)
    {
        int r = i-w;
        int insert_val;
        if(r >= 0)
        {
            insert_val = p;
        }
        else
        {
            insert_val = 0;
        }
        vec.push_back(insert_val);
    }
    //print_vec(vec);
    for(int i=1;i<n;i++)
    {
        fin>>w>>p;
        for(int j=0;j<=g;j++)
        {
            int r = j-w;
            int insert_val;
            if(r >= 0)
            {
                insert_val = max(p+vec[r],vec[j]);
            }
            else
            {
                insert_val = max(0,vec[j]);
            }
            vec2.push_back(insert_val);
        }
        vec = vec2;
        //print_vec(vec2);
        vec2.clear();
    }
    fout<<vec2[g];
}