#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gr,i,x[15005],j,v[5005],g[5005];
int main(){
    fin>>n>>gr;
    for(i=1;i<=n;i++)
        fin>>g[i]>>v[i];
    for(i=1;i<=n;i++)
        for(j=gr-g[i];j>=0;j--)
            if(x[j+g[i]]<x[j]+v[i])
                x[j+g[i]]=x[j]+v[i];
    fout<<x[gr];
    return 0;
}