#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int gMax = 10005;
int dp[3][gMax]; ///din primele i, greutatea j
int main()
{
    int n, s, cost, pro;
    f >> n >> s;
    int lin = 0;
    for(int i = 1; i <= n; i++, lin = 1 - lin) {
        f >> cost >> pro;
        for(int j = 0; j <= s; j++) {
            dp[lin][j] = dp[1 - lin][j];
            if(j - cost >= 0) {
                dp[lin][j] = max(dp[lin][j], dp[1 - lin][j - cost] + pro);
            }
        }
    }
    lin = 1 - lin;
    int ans = 0;
    for(int i = 0; i <= s; i++) {
        ans = max(ans, dp[lin][s]);
    }
    g << ans << "\n";
    return 0;
}