#include <fstream>
#define DIM 5005
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G;
struct obiect{
    int w,p;     //greutatea,respectiv profitul
};
obiect v[DIM];
int dp[10005];
int main()
{
    fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>v[i].w>>v[i].p;
    dp[0]=1; //profitul maxim prin care pot obtine greutatea i
    int sol=-1;
    for(int i=1;i<=N;i++){
        for(int j=G;j>=0;j--)
        if(dp[j]!=0 && j+v[i].w<=G){
                dp[j+v[i].w]=max(dp[j+v[i].w],dp[j]+v[i].p);
                sol=max(sol,dp[j+v[i].w]);
        }
    }
    fout<<sol-1;
    return 0;
}