#include <stdio.h>
#define MAXN 5005
#define MAXG 10005
#define MAX(a, b) (((a) > (b))?(a):(b))
using namespace std;

int n, g, w[MAXN], p[MAXN], dp[MAXG];

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; j >= w[i]; j--)
            dp[j] = MAX(dp[j], dp[j - w[i]] + p[i]);

    int sol = 0;
    for(int i = 0; i <= g; i++)
        sol = MAX(sol, dp[i]);

    printf("%d\n", sol);

    return 0;
}