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