#include <stdio.h>          // printf(), scanf()

#define MAX_N 100
#define MAX_W 10000 
#define max(a, b) ((a) > (b) ? (a) : (b))

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

int
solve()
{
	int i, j;

	for (j = 0; j <= W; ++j)
		dp[0][j] = 0;

	for (i = 0; i < n; ++i)
	{
		for (j = 0; j <= W; ++j)
		{
			if (j < w[i])
				dp[i + 1][j] = dp[i][j];
			else
				dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
		}
	}

	return dp[n][W];
}

int
main(int argc, char** argv)
{
	int i;

	scanf("%d %d", &n, &W);
	for (i = 0; i < n; ++i)
		scanf("%d %d", &v[i], &w[i]);

	printf("%d\n", solve());
	return 0;
}