1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <iostream>
using namespace std;
long long n,M,dp[2001];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> M;
    for(int i = 0,h,c; i < n; i++) {
        cin >> h >> c;
        for(int j = c; j <= M; j++) dp[j] = max(dp[j-c]+h, dp[j]);
    }
    cout << dp[M] << '\n';
}