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