#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int sol,n,G,w[10001],p[10001],d[10001];

int main(){
 fin>>n>>G;
 for(int i=1;i<=n;i++){
    fin>>w[i]>>p[i];
 }
 d[0]=1;
 for(int i=1;i<=n;i++){
    for(int j=G;j>=0;j--){
        if(d[j]&&j+w[i]<=G){
            d[j+w[i]]=max(d[j]+p[i],d[j+w[i]]);
            sol=max(sol,d[j+w[i]]);
        }
    }
 }
 fout<<sol-1;
}