#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
long long v[1001][1001]={0};
int main()
{
    int n,g,d[1000]={0},val[1000]={0},smx,m[5][10001]={0};
    fi>>n>>g;
    for(int i=1;i<=n;i++){
        fi>>d[i]>>val[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=g;j++){
            if(j>=d[i]){
                if((m[1][j-d[i]]+val[i])>m[1][j])
                    m[2][j]=m[1][j-d[i]]+val[i];
                else if((m[1][j-d[i]]+val[i])<m[1][j])
                    m[2][j]=m[1][j];
            else
                m[2][j]=m[1][j];
            }
        }
        for(int j=1;j<=g;j++)m[1][j]=m[2][j];
    }
    fo<<m[2][g];
}