#include <bits/stdc++.h>

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

int n, m, w[5001], v[5001]; bool vf=0;
int main(){
    f>>n>>m;
    std::vector<int> dp(m+1, 0);
    for(int i=1; i<=n; ++i)
        f>>w[i]>>v[i];
    for(int i=1; i<=n; ++i)
        for(int j=m; j>=w[i]; --j)
            if(dp[j] < dp[j-w[i]]+v[i])
                dp[j] = dp[j-w[i]]+v[i];
    g<<dp[m]<<'\n';
    return 0;
}