#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
long long dp[10004];
int main()
{
    long long n,g,w,p,i,j,maxi=0;
    in>>n>>g;
    for(i=0;i<n;i++){
        in>>w>>p;
        for(j=g;j>=w;j--){
            if(dp[j-w]>0 && dp[j-w]+p>dp[j]){
                dp[j]=dp[j-w]+p;
                if(dp[j]>maxi){
                    maxi=dp[j];
                }
            }
        }
        if(dp[w]<p){
            dp[w]=p;
            if(dp[w]>maxi){
                maxi=dp[w];
            }
        }
    }
    out<<maxi;
    return 0;
}