/*
Problema rucsacului.
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX     10000

#define max(a, b) ((a > b) ? a : b)

int n, g;
int w[MAX], p[MAX], sol_part[MAX];
int p_max;

void afla_profit () {
    int i, j;

    p_max = 0;
    for (i = 0; i < MAX; i++)
        sol_part[i] = 0;

    for (i = 0; i < n; i++) {
        for (j = g - w[i]; j >= 0; j--) {
            if (sol_part[j] + p[i]) {
                sol_part[j + w[i]] = max(sol_part[j + w[i]], p[i] + sol_part[j]);
                p_max = max(p_max, sol_part[j + w[i]]);
            }
        }
    }
}

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

    int i;
    scanf("%d %d", &n, &g);
    for (i = 0; i < n; i++) 
        scanf("%d %d", &w[i], &p[i]);
    
    afla_profit();
    printf("%d\n", p_max);

    return 0;
}