#include <cstdio>
using namespace std;

const int MAXN = 5005;
const int MAXG = 10005;

int n, g, ans;
int dp[MAXG], W[MAXN], P[MAXN];

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &g);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &W[i], &P[i]);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = g - W[i]; j >= 0; --j)
        {
            if (dp[j + W[i]] < dp[j] + P[i])
			{
				dp[j + W[i]] = dp[j] + P[i];
				if (dp[j + W[i]] > ans)
					ans = dp[j + W[i]];
			}
        }
    }
    printf("%d", ans);
    return 0;
}