#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){
    if (n==0) return 0;
    if (dp[n][g]!=-1) return dp[n][g];
    dp[n][g]= rucsac(n-1,g);
    if (g-w[n]>=0) dp[n][g]=max(rucsac(n-1,g-w[n])+p[n], dp[n][g]);
    return dp[n][g];
}
int main(){
    fin>>n>>g;
    for (int i=1;i<=n;i++) fin>>w[i]>>p[i];
    int rez=0;
    for(int i=0;i<=1000;i++)
        for (int j=0;j<=1000;j++) dp[i][j]=-1;
    for (int i=0;i<=g;i++)
        rez=max(rez, rucsac(n,i));
    fout<<rez;
}