#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5e3+2;
const int VMAX = 1e4+2;
int n,g,w[NMAX],c[NMAX],dp[2][VMAX];

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

int main()
{
    fin >> n >> g;
    for(int i = 1; i <= n; i++){
        fin >> w[i] >> c[i];
        int curr = (i&1), prev = !curr;
        for(int j = 0; j <= g; j++){
            dp[curr][j+w[i]] = max({dp[curr][j+w[i]], dp[prev][j+w[i]], c[i]+dp[prev][j]});
        }
    }
    fout << dp[(n&1)][g];
    return 0;
}