#include <fstream>

using namespace std;

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

int dp[10005];
struct obiect
{
    int val,g;
}v[5005];

int main()
{
    int n,G;
    in>>n>>G;
    for(int i=1;i<=n;i++)
        in>>v[i].g>>v[i].val;
    for(int i=1;i<=n;i++)
        for(int j=G;j>=v[i].g;j--)
        {
            dp[j]=max(dp[j-v[i].g]+v[i].val,dp[j]);
        }
    out<<dp[G];
    return 0;
}