/* 
 * File:   main.c
 * Author: mihai
 *
 * Created on December 22, 2011, 11:32 PM
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a, b) (a) > (b) ? (a) : (b)

/*
 * 
 */
int main(int argc, char** argv) {
    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);
    

    int i, j, k;
    const int n, g;
    scanf("%d %d", &n, &g);
    int a[2][n];
    int tab[2][g + 1];
    memset(tab[0], 0, (g + 1) * sizeof (int));
    memset(tab[1], 0, (g + 1) * sizeof (int));
    for (i = 0; i < n; i++)
        scanf("%d %d", &a[0][i], &a[1][i]);
    for (j = 0; j < n; j++) {
        for (i = 0; i <= g; i++) {
            if (i - a[0][j] >= 0)
                tab[1][i] = max(tab[0][i], tab[0][i - a[0][j]] + a[1][j]);
            else
                tab[1][i] = tab[0][i];
            //for (k = 0; k <= g; k++) tab[0][k] = tab[1][k];
        }
        for (k = 0; k <= g; k++) tab[0][k] = tab[1][k];
    }
    printf("%d", tab[1][g]);
    return 0;
}