#include <iostream>
#include<bits/stdc++.h>

using namespace std;

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

int n, G, dp[5001];

int main()
{
    in>>n>>G;
    int w, p;
    for(int i=1; i<=n; i++)
    {
        in>>w>>p;
        for(int j=G; j>=w; j--)
            if(dp[j]<dp[j-w]+p)
                dp[j]=dp[j-w]+p;
    }
    out<<dp[G];
    return 0;
}