/***************

    ~LeTeutz~
    100p - O(N*W) timp
         - O(W) memorie

****************/

#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int NMAX = 5001;

int N,G,maximum;
int V[NMAX],W[NMAX],dp[2*NMAX];

int main() {
    f>>N>>G;
    for(int i=1; i<=N; i++)
        f>>W[i]>>V[i];

    for(int i=1; i<=N; i++)
        for(int j=G-W[i]; j>=0; j--)
            if( dp[j+W[i]] < dp[j] + V[i]) {
                dp[j+W[i]] = dp[j] + V[i];
                maximum = max( maximum, dp[j+W[i]]);
            }

    g<<dp[G]<<"\n";
    return 0;
}