//problema rucsacului fractionar
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
struct Obiect{
    int greutate, valoare, raport;
};
vector<Obiect> v(100);
bool cmp(Obiect a, Obiect b){
    return a.raport > b.raport;
}
int main(){
    int n, capacitate;
    f>>n>>capacitate;
    for(int i=0; i<n; i++){
        f>>v[i].valoare;
    }
    for(int i=0; i<n; i++){
        f>>v[i].greutate;
        v[i].raport = v[i].valoare/v[i].greutate;
    }
    sort(v.begin(), v.end(), cmp);
    float profit = 0;
    for(int i=0; i<n; i++){
        if(capacitate >= v[i].greutate){
            profit += v[i].valoare;
            capacitate -= v[i].greutate;
        }
        else{
            profit += v[i].raport*capacitate;
            break;
        }
    }
    g<<profit;
    return 0;
}
*/

//problema rucsacului discreta
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int dp[5001][10001],n,G,v,gr;
int main()
{
    f>>n>>G;
    for(int i=1;i<=n;i++)
    {
        f>>gr>>v;
        for(int j=0;j<=G;j++)
        {
            if(j<gr)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-gr]+v);
        }
    }
    g<<dp[n][G];
    return 0;
}