#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MAX_N=5001;
const int MAX_G=10001;

int wt[MAX_N],val[MAX_N];
int obiecte,greutate;
int dp[MAX_N][MAX_G];

int maxim(int a,int b){
    return(a>b ? a:b);
}

void citire(){
    in>>obiecte>>greutate;
    int a,b;
    for(int i=1;i<=obiecte;i++){
        in>>a>>b;
        wt[i]=a;
        val[i]=b;
    }
}

void solve_dp(){
    for(int i=1;i<=obiecte;i++){
        for(int j=1;j<=greutate;j++){
            int pick=0;
            if(wt[i]<=j){
                pick=val[i]+dp[i-1][j-wt[i]];
            }
            int notpick=dp[i-1][j];
            dp[i][j]=maxim(pick,notpick);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    out.tie(NULL);
    citire();
    solve_dp();
    out<<dp[obiecte][greutate];
}