//DP Knapsack 0-1 Bottom Up
#include<bits/stdc++.h>
using namespace std;
int W[1001], V[1001];
long long dp[1001][1001];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> W[i] >> V[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 1) {
if (W[i] <= j) dp[i][j] = V[i];
else dp[i][j] = 0;
} else {
if (W[i] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
else dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][m] << "\n";
}
Ly9EUCBLbmFwc2FjayAwLTEgQm90dG9tIFVwCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBXWzEwMDFdLCBWWzEwMDFdOwpsb25nIGxvbmcgZHBbMTAwMV1bMTAwMV07CgppbnQgbWFpbigpIHsKCWludCBuLCBtOwoJY2luID4+IG4gPj4gbTsKCWZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCWNpbiA+PiBXW2ldID4+IFZbaV07Cgl9Cglmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKCQlmb3IgKGludCBqID0gMDsgaiA8PSBtOyBqKyspIHsKCQkJaWYgKGkgPT0gMSkgewoJCQkJaWYgKFdbaV0gPD0gaikgZHBbaV1bal0gPSBWW2ldOwoJCQkJZWxzZSBkcFtpXVtqXSA9IDA7CgkJCX0gZWxzZSB7CgkJCQlpZiAoV1tpXSA8PSBqKSBkcFtpXVtqXSA9IG1heChkcFtpIC0gMV1bal0sIGRwW2kgLSAxXVtqIC0gV1tpXV0gKyBWW2ldKTsKCQkJCWVsc2UgZHBbaV1bal0gPSBkcFtpIC0gMV1bal07CgkJCX0KCQl9Cgl9Cgljb3V0IDw8IGRwW25dW21dIDw8ICJcbiI7Cn0=