#include <iostream>
#include <fstream>

using namespace std;

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

int n, g, sol;
int v[5001], p[5001], d[10001];

int main (){
      fin>>n>>g;
      for(int i=1; i<=n; i++)
            fin>>v[i]>>p[i];

      d[0]=1;
      for(int i=1; i<=n; i++)
            for(int j=g; j>=0; j--)
                  if(d[j] != 0 && j + v[i] <= g){
                        d[j + v[i]]=max(d[j + v[i]], d[j]+p[i]);
                        sol=max(sol, d[j+v[i]]);
                  }

      fout<<sol-1;
      return 0;
}