#include <cstdio>
#include <algorithm>

using namespace std;

struct obj{
    int w, p;
};

obj object[5001];

int n;

int dinam[10001];

void print(){
    for(int i = 1;i <= n;i++)
        printf("%d %d\n", object[i].w, object[i].p);
}


const int inf = 500000000;

int main()
{
    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);
    int G;
    scanf("%d%d", &n ,&G);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &object[i].w, &object[i].p);
    dinam[0] = 0;
    for(int i = 1; i <= G; i++)
        dinam[i] = -inf;
    for(int i = 1; i <= n; i++){
        for(int j = G; j >= object[i].w; j--){
            dinam[j] = max(dinam[j], dinam[j - object[i].w] + object[i].p);
        }
    }
    printf("%d", dinam[G]);
    return 0;
}