#include <bits/stdc++.h>

using namespace std;

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

int n, w;
vector<pair<int, int>> v;
int **a;

bool comp (pair<int, int> a, pair<int, int> b)
{
    return a.first<b.first;
}
void alloc_matrix()
{
    a=(int**)malloc((n+1)*sizeof(int*));
    for(int i=0; i<=n; i++)
        a[i]=(int*)malloc((w+1)*sizeof(int));
}

void free_matrix()
{
    for(int i=0; i<=n; i++)
        free(a[i]);
    free(a);
}

int max_profit()
{
    for(int i=0; i<=w; i++)
        a[0][i]=0;
    for(int i=0; i<=n; i++)
        a[i][0]=0;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<v[i-1].first; j++)
            a[i][j]=a[i-1][j];
        for(int j=v[i-1].first; j<=w; j++)
            a[i][j]=max(a[i-1][j], v[i-1].second+a[i-1][j-v[i-1].first]);
    }
    return a[n][w];
}
int main()
{
    int x, y;
    f>>n>>w;
    alloc_matrix();
    /// x->weight
    /// y->profit
    while(f>>x>>y)
        v.push_back(make_pair(x, y));

    sort(v.begin(), v.end(), comp); /// sort vector in ascending oder by weight

    g<<max_profit();

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