#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;
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        fin >> w[i] >> c[i];
        int curr = (i&1), prev = !curr;
        memcpy(dp[curr], dp[prev], sizeof(dp[prev]));
        for(int j = 0; j+w[i] <= g; j++){
            if(dp[prev][j] != -1){
                dp[curr][j+w[i]] = max(dp[curr][j+w[i]], c[i]+dp[prev][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= g; i++){
        ans = max(ans, dp[(n&1)][i]);
    }
    fout << ans;
    return 0;
}