#include <iostream>
#include <fstream>
#define INF -1

using namespace std;

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

int dp[10005], f[10005];
int sol, nxt, far, mark;
int n, lim;
int v, g;

int main (){
    fin>>n>>lim;

    for(int i=1; i<=lim; i++)
        dp[i]=INF;



    for(int i=1; i<=n; i++){

        fin>>g>>v;
        mark=far;

        for(int j=mark; j>=0; j--){
            if(dp[j] != INF && f[j] != i){

                nxt=j + g;

                if(nxt <= lim && dp[j] + v > dp[nxt]){
                    dp[nxt]=dp[j] + v;
                    f[nxt]=i;
                    if(nxt > far)
                        far=nxt;
                }
            }
        }
    }
    for(int i=lim; i>=1; i--)
        if(dp[i] > sol && dp[i] != INF)
            sol=dp[i];

    fout<<sol;
    return 0;
}