#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int nmax = 1e4+5;
int dp[2][nmax],n,gmax;
int greutate[1005],valoare[1005];
void read_input(){
    fin >> n >> gmax;
    for(int i =1; i <=n; i++){
        fin >> greutate[i] >> valoare[i];
    }
}
void dinamica(){
    int linie = 0;
    for(int i = 1; i <=n; i++,linie ^= 1){
        for(int g_aux = 0; g_aux <= gmax; g_aux++){
            dp[linie][g_aux] = dp[!linie][g_aux];
            if(greutate[i] <= g_aux){
                dp[linie][g_aux] = max(dp[linie][g_aux],
                dp[!linie][g_aux-greutate[i]]+valoare[i]);
            }
        }
    };
    fout << dp[!linie][gmax];
}
int main()
{
    read_input();
    dinamica();
    return 0;
}