#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

ifstream F("rucsac.in");
ofstream G("rucsac.out");

int n, W, dp[2][10003];
pair<int, int> p[5003];

int main()
{
    F >> n >> W;
    for(int i = 1; i <= n; ++ i) F >> p[i].f >> p[i].s;
    sort(p+1, p+n+1);
    for(int i = 1; i <= n; ++ i)
        if(i % 2)
            for(int j = 1; j <= W; ++ j)
                if(j >= p[i].f)
                    dp[0][j] = max(dp[1][j], dp[1][j-p[i].f]+p[i].s);
                else dp[0][j] = dp[1][j];
        else
            for(int j = 1; j <= W; ++ j)
                if(j >= p[i].f)
                    dp[1][j] = max(dp[0][j], dp[0][j-p[i].f]+p[i].s);
                else dp[1][j] = dp[0][j];
    G << dp[1][W];
    return 0;
}