#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main(){ int N, W, w, v; cin >> N >> W; vector> dp(N+1, vector(W+1)); for (int i=1; i<=N; i++){ cin >> w >> v; for (int j=0; j<=W; j++){ dp[i][j] = max(dp[i-1][j], dp[i][j]); if (j-w>=0) dp[i][j] = max(dp[i-1][j-w]+v, dp[i][j]); } } cout << dp[N][W] << endl; return 0; }