#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000
#define MAXG 10000

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

int dp[2][MAXG + 1];
int gr[MAXN + 1];
int pr[MAXN + 1];

int main(){
    int n,g;
    int lin;
    int i,j;

    fin >> n >> g;

    for (i = 1; i <= n; i ++) {
        fin >> gr[i] >> pr[i];
    }

    lin = 0;
    for (i = 1; i <= n; i ++) {

        lin = 1 - lin;
        for (j = 1; j <= g; j ++) {
            if (j < gr[i]) {
                dp[lin][j] = dp[1 - lin][j];
            }
            else {
                dp[lin][j] = max(dp[1 - lin][j - gr[i]] + pr[i],dp[1 - lin][j]);
            }
        }
    }

    fout << dp[lin][g];

}