#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2,popcnt")

using namespace std;

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

const int INF = 2e9;
const int MAX_N = 5005;
const int MAX_G = 10005;
int n, g, w[MAX_N], p[MAX_N];
int maxProfit[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>>w[i]>>p[i];

    maxProfit[0] = 0;
    for(int weight=1; weight<=g; weight++)
        maxProfit[weight] = -1;

    for(int i=1; i<=n; i++)
        for(int weight=g-w[i]; weight>=0; weight--)
            if(maxProfit[weight] >= 0)
                maxProfit[weight + w[i]] = max(maxProfit[weight + w[i]], maxProfit[weight] + p[i]);

    int sol = 0;
    for(int weight=0; weight<=g; weight++)
        sol = max(sol, maxProfit[weight]);
    fout<<sol;
    return 0;
}