#include <bits/stdc++.h>
#define INF 0x3f3f3f3f  // INF mare pentru long long
#define mod 666013
using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,G;
    f>>n>>G;
    vector<int>w(n+1),p(n+1);
    for(int i=1; i<=n; ++i)
        f>>w[i]>>p[i];
    vector<vector<int>>dp(2,vector<int>(G));
    int curent=1;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=G; ++j){
            if(j-w[i]>=0)
                dp[curent][j]=max(dp[1-curent][j],dp[1-curent][j-w[i]]+p[i]);
            else dp[curent][j]=dp[1-curent][j];
        }
        curent=1-curent;
    }
    g<<dp[1-curent][G];

    return 0;
}