#include<bits/stdc++.h>
#define N 5005
using namespace std;

int n,g,a[N],p[N];
int dp[2][2*N];
bool u;

int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");

    cin>>n>>g;
    for (int i=1; i<=n; i++) cin>>a[i]>>p[i];

    for (int i=1; i<=n; i++, u=!u) {
        for (int j=1; j<=g; j++) {
            dp[u][j] = dp[!u][j];
            if (j>=a[i] && p[i] + dp[!u][j-a[i]]>dp[u][j]) dp[u][j] = p[i] + dp[!u][j-a[i]];
        }
    }
    cout<<dp[!u][g];

    return 0;
}