#include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 struct s

 {

     int c,val;

 }p[];

 using namespace std;

 int dp[];

 int main()

 {

     int sum,v;

     while(cin>>sum>>v){

             memset(dp,,sizeof(dp));

         for(int i=;i<sum;i++){

             cin>>p[i].c>>p[i].val;

         }

     for(int i=;i<sum;i++){

         for(int j=v;j>=p[i].c;j--){

             dp[j]=max(dp[j],dp[j-p[i].c]+p[i].val);

         }

     }

     cout<<dp[v]<<endl;}

 }