#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int nMax = 10003;
int dp[4][nMax];
int main()
{
    int n, S, greu, profit;
    f >> n >> S;
    int lin = 1;
    for(int i = 1; i <= n; i++, lin = 1 - lin) {
        f >> greu >> profit;
        for(int j = 0; j <= S; j++) {
            dp[lin][j] = dp[1 - lin][j];
            if(j - greu >= 0) {
                dp[lin][j] = max(dp[lin][j], dp[1 - lin][j - greu] + profit);
            }
        }
    }
    int ans = 0;
    lin = 1 - lin;
    for(int i = 0 ; i <= S; i++) {
        ans = max(ans, dp[lin][i]);
    }
    g << ans << "\n";
    return 0;
}