#include <stdio.h>
using namespace std;

int n, g_max;
int pr[5010];
int gr[5010];
int a[5010][10020];

void citeste() {
     scanf("%d%d", &n, &g_max);
     for (int i = 1; i <= n; i++) {
         scanf("%d%d", &gr[i], &pr[i]);
     }
}

int max(int a, int b) {
    return (a > b ? a : b);
}

int rezolva() {
    // Completez restul matricei
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= g_max; j++) {
            if (gr[i] <= j) {
               a[i][j] = max(a[i-1][j], a[i-1][j - gr[i]] + pr[i]);
            } else {
               a[i][j] = a[i-1][j];
            }
        }
    }
    return a[n][g_max];
}

void afiseaza(int rez) {
     printf("%d",rez);   
}

int main()
{
    int rez;
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    citeste();
    rez = rezolva();
    afiseaza(rez);
}