#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 5005;
const int MAX_G = 10005;
int n, g;
int weight[MAX_N], profit[MAX_G];

struct rucsac{
    bool active;
    int max_profit;
} dp[MAX_G];

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>weight[i]>>profit[i];

    dp[0].active = true;
    dp[0].max_profit = 0;
    for(int crt_weight=1; crt_weight<=g; crt_weight++){
        dp[crt_weight].active = false;
        dp[crt_weight].max_profit = -1;
    }

    for(int i=1; i<=n; i++)
        for(int crt_weight=g, nxt_weight; crt_weight>=0; crt_weight--)
            if(dp[crt_weight].active == true){
                nxt_weight = crt_weight + weight[i];
                if(nxt_weight <= g && dp[crt_weight].max_profit + profit[i] > dp[nxt_weight].max_profit){
                    dp[nxt_weight].active = true;
                    dp[nxt_weight].max_profit = dp[crt_weight].max_profit + profit[i];
                }
            }

    int sol_profit = -1;
    for(int crt_weight=0; crt_weight<=g; crt_weight++)
        sol_profit = max(sol_profit, dp[crt_weight].max_profit);
    fout<<sol_profit;
    return 0;
}