#include <cstdio>
#include <climits>
#define nMax 5120
#define wMax 10240

using namespace std;

int n,maxWeigth,weigth[nMax],price[nMax],option[wMax];

int takeMax(int x,int y) {
    return (x>y)*(x-y)+y;
}

void read() {
    int i;
    scanf("%d%d",&n,&maxWeigth);
    for(i=1;i<=n;++i) {
        scanf("%d%d",&weigth[i],&price[i]);
    }
}

void play(int objPos) {
    int i;
    for(i=maxWeigth;i>0;--i) {
        if(i-weigth[objPos]>=0) {
            option[i]=takeMax(option[i],option[i-weigth[objPos]]+price[objPos]);
        }
    }
}

void solve() {
    int i;
    for(i=1;i<=n;++i) {
        play(i);
    }
}

void display() {
    printf("%d",option[maxWeigth]);
}

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    read();
    solve();
    display();
    return 0;
}