#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>

#define MOD 666013

using namespace std;

ifstream cin("rucsac.in") ;
ofstream cout("rucsac.out") ;

struct costum
{

    int val, g ;

    double r ;

    costum(int a, int b)
    {

        g = a ;
        val = b ;

        r = (double)val / g ;

    }

    void afis()
    {

        cout << g << " " << val << " " << r << endl ;

    }

};

bool ord(costum a, costum b)
{

    if(a.r != b.r)return a.r > b.r ;

    if(a.g != b.g)return a.g < b.g ;

    return a.val > b.val ;

}

vector<costum> v ;

int m[10009] ;

int main()
{

    int n, gmax ;

    cin >> n >> gmax ;

    for(int f = 1, a, b ; f <= n ; f ++)
    {

        cin >> a >> b ; /// g si apoi val

        costum c(a, b) ;

        v.push_back(c) ;

    }

    /// pentru fiecare v[f] luam fiecare greutate posibila de obtinut pana la gmax
    /// si putem sa zicem costul care il ia pana acolo

    for(int f = 0 ; f < n ; f ++)
    {

        for(int e = gmax ; e ; e --)
        {

            /// greutatea e este formata din suma maxima pentr e - v[f] + valoarea lui v[f]

            if(e >= v[f].g)m[e] = max(m[e], m[e - v[f].g] + v[f].val) ;

        }

    }

    int mx = 0 ;

    for(int f = 1 ; f <= gmax ; f ++)
        mx = max(mx, m[f]) ;

    cout << mx ;

    return 0;

}