#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
int main()
{
	int n, W;
	int v[101], w[101];
	int dp[101][1001];
	cin >> n >> W;
	for (int i = 0; i < n; i++){
		cin >> v[i] >> w[i];
	}
	for (int i = 1; i <= n; i++){
		for (int i2 = 0; i2 <= W; i2++){
			if (i2 - w[i - 1] >= 0)dp[i][i2] = max(dp[i - 1][i2], dp[i][i2 - w[i]] + v[i]);
			else dp[i][i2] = dp[i - 1][i2];
		}
	}
	cout << dp[n][W] << endl;
}