#include <iostream>
#include <cstdio>
using namespace std;

const int N_max = 5000;
const int G_max = 10000;

int weight[N_max+1], price[N_max+1];
int sol[G_max+1]; // sol[i] == PROFITUL MAXIM AVAND GREUTATEA i
int last[G_max+1]; //ULTIMUL OBIECT ALES

int N, G, bestSum;

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    int i, j;

    scanf("%d %d", &N, &G);
    for(i = 1; i <= N; i++)
        scanf("%d %d", &weight[i], &price[i]);

    last[0] = -1;

    for(i = 1; i <= N; i++)
        for(j = G-weight[i]; j >= 0; j--)
            if(last[j] != 0)
                if(last[j+weight[i]] == 0 || sol[j+weight[i]] < sol[j] + price[i])
                {
                    sol[j + weight[i]] = sol[j] + price[i];
                    last[j + weight[i]] = i;

                    if(bestSum < sol[j + weight[i]])
                        bestSum = sol[j + weight[i]];
                }

    printf("%d", bestSum);

    return 0;
}