#include <iostream>
#include <fstream>
#define INF 99999
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n , greutate[5000+1] , valoare[ 5000+1] , a[2][10001];
int W ;
int main()
{
    in >> n >> W ;
        for ( int i =1 ; i <= n ; ++ i )
        {
             in >> greutate[i] >> valoare[ i ];
        }
 int l = 0 ;
         for ( int i = 1 ; i <= n ; ++ i )
         {
                for ( int w = 1 ; w <= W ; ++ w )
                {
                    a [ 1-l ] [ w ] = a [ l ] [w ] ;
                    // initial nu l iau
                    if ( greutate [i] <= w )
                    {
                        a[1-l][w] = max (a[1-l][w] , valoare[i] + a[l][w-greutate[i]]);
                    }

                }
              l = 1 - l ;
         }
 out << a[l][W];



    return 0;
}