#include <bits/stdc++.h>
#define mod 666013
using namespace std;
int n,g,w[10005],p[10005],dp[10005];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int rucsac(int n, int g){
    for (int i=1;i<=n;i++){
        for (int j=g;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
        }
    }
    int rez=0;
    for (int j=0;j<=g;j++)
        rez=max(rez,dp[j]);
    return rez;
}
int main(){
    fin>>n>>g;
    for (int i=1;i<=n;i++) fin>>w[i]>>p[i];
    int rez=0;
    rez=max(rez, rucsac(n,g));
    fout<<rez;
}