/// rucsac
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>

#define out output();
#define NMax 5005
#define GMax 10005

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,w;
int greu[GMax];
bitset<NMax> used[GMax];
int G[NMax], V[NMax];

void output() {
    for (int i=1;i<=w;i++)
        cout<<greu[i]<<' ';
    cout<<endl;
}

void solve() {
    for (int i=1;i<=n;i++)
        if (G[i] <= w) {
            if (greu[G[i]] < V[i]) {
                greu[G[i]] = V[i];
                used[G[i]].reset();
                used[G[i]][i] = 1;
            }
        }

    for (int i=1;i<=w;i++)
        for (int j=1;j<=n;j++)
            if (i + G[j] <= w && !used[i][j]) {
                if (greu[i+G[j]] < greu[i] + V[j]) {
                    greu[i+G[j]] = greu[i] + V[j];
                    for (int k=1;k<=n;k++)
                        used[i+G[j]][k] = used[i][k];
                    used[i+G[j]][j] = 1;
                }
            }
    // out
    g<<greu[w]<<'\n';
}

void read() {
    f>>n>>w;
    for (int i=1;i<=n;i++)
        f>>G[i]>>V[i];
}

int main() {

    read();
    solve();

    f.close(); g.close();
    return 0;
}