Untitled

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5, maxw = 1e5 + 5;
long long dp[maxn][maxw], wei[maxn], val[maxn];

int main(){
	int n, w;
	cin >> n >> w;
	for(int i = 1; i <= n; i++){
		cin >> wei[i] >> val[i];
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= w; j++){
			if(j - wei[i] >= 0){
				dp[i][j] = max(dp[i - 1][j - wei[i]] + val[i], dp[i - 1][j]);
			}
			else{
				dp[i][j] = dp[i - 1][j];
			}
			//cout << dp[i][j] << '\n';
		}
	}
	
	cout << dp[n][w];
}