#include<bits/stdc++.h>
using namespace std;

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


int n,capacitate,profit[5000],greutate[5000];

void read()
{
    in>>n>>capacitate;
    for(int i=0; i<n; i++)
    {
        in>>greutate[i]>>profit[i];
    }
}

int dp[2][10001];

int dpp()
{
    for(int i=1; i<=n; i++)
    {
        for(int k=0; k<=capacitate; k++)
        {
            dp[i%2][k]=dp[(i-1)%2][k];
            if(greutate[i-1]<=k)
            {
                dp[i%2][k]=max(dp[i%2][k],profit[i-1]+dp[(i-1)%2][k-greutate[i-1]]);
            }
        }
    }
    return dp[n%2][capacitate];

}

int main()
{
    read();
    out<<dpp();
}