#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int D[10001],g[10001],v[10001];
int n,G,sol;

int main(){
    fin>>n>>G;
    for(int i=1;i<=n;i++){
        fin>>g[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        D[i]=-1;
    }
    D[0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=G;j>=0;j--){
            if(D[j]!=-1 && j+g[i]<=G && D[j+g[i]]<D[j]+v[i]){
                    D[j+g[i]]=D[j]+v[i];
            }
        }
    }
    for(int i=0;i<=G;i++){
        if(sol<D[i]){
            sol=D[i];
        }
    }
    fout<<sol;
}