#include using namespace std; #include using namespace atcoder; using ll = long long; using ld = long double; using P = pair; using Graph = vector>; using vi = vector; using vl = vector; using vll = vector; using vvi = vector; using vvl = vector; using vvll = vector; using vs = vector; using vc = vector; using vvc = vector; using pll = pair; using vpll = vector; using mint = modint1000000007; const long double EPS = 1e-18; const long long INF = 1e18; const long double PI = acos(-1.0L); #define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++) #define rep(i, n) for (ll i = (0); i < (ll)(n); i++) #define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++) #define repd(i, n) for (ll i = n - 1; i >= 0; i--) #define rrepd(i, n) for (ll i = n; i >= 1; i--) #define ALL(n) begin(n), end(n) #define IN(a, x, b) (a <= x && x < b) #define INIT \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); template inline T CHMAX(T& a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; } int main() { vvll dp(1010, vll(1010, 0)); ll N, I; cin >> N >> I; vll s(1010), a(1010); rrep(i, N) { cin >> s[i] >> a[i]; } rrep(i, N) { rep(j, 1005) { CHMAX(dp[i][j], dp[i - 1][j]); if (j >= s[i]) { CHMAX(dp[i][j], dp[i - 1][j - s[i]] + a[i]); } } } cout << dp[N][I] << endl; return 0; }