#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G;

struct Object
{
    int weight;
    int profit;
};
Object* objects=new Object[N];
int knapsack(int N, int G, Object* objects)
{
    int** dp=new int*[N + 1];
    for (int i=0; i<=N; i++)
        dp[i]=new int[G + 1];

    for (int i=0; i<=N; i++)
    {
        for (int j=0; j<=G; j++)
            dp[i][j]=0;
    }

    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=G; j++)
        {
            if (objects[i-1].weight<=j)
                dp[i][j]=max(objects[i-1].profit + dp[i-1][j-objects[i-1].weight], dp[i-1][j]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }

    int maxProfit=dp[N][G];

    for (int i=0; i<=N; i++)
        delete[] dp[i];
    delete[] dp;

    return maxProfit;
}

int main()
{

    
    fin>>N>>G;

    Object* objects=new Object[N];
    for (int i=0; i < N; i++)
        fin>>objects[i].weight>>objects[i].profit;

    int maxProfit=knapsack(N, G, objects);

    fout<<maxProfit<<"\n";

    fin.close();
    fout.close();

    delete[] objects;

    return 0;
}