#include <iostream>
#include <fstream>

const int MAXN = 5e3 + 5,MAXG = 1e4 + 5;

using namespace std;

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

int dp[MAXG],n,maxg,cost[MAXN],weight[MAXN];
///dp[i] = suma maxima pe care o pot face care are greutatea <= i

int main()
{
    in>>n>>maxg;
    for(int i = 1; i <= n; i++)
        in>>weight[i]>>cost[i];
    for(int i = 1; i <= n; i++)
        for(int j = maxg - weight[i]; j >= 0; j--)
            dp[j + weight[i]] = max(dp[j + weight[i]],dp[j] + cost[i]);
    out<<dp[maxg];
    return 0;
}