#include <stdio.h>
#include <iostream>

int greutate[5000], profit[5000];
int C[2][10000];

int main()
{
	freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

	int n, i, capacitate, l, j;

    scanf("%d %d", &n, &capacitate);

    for(i = 1; i <= n; ++i)
        scanf("%d %d", greutate + i, profit + i);

	l = 0;
	for (i=1;i<=n;++i)
	{
		l = 1 - l;

		for (j = 0;j <= capacitate;++j)
		{
			C[l][j] = C[1 - l][j];

			if (greutate[i] <= j)
				C[l][j]=
                    std::max(C[l][j],
                             C[1 - l][j-greutate[i]]+profit[i]);
		}
	}

	printf("%d",C[l][capacitate]);
	return 0;
}