1. #include <iostream>
    2. #include <functional>
    3. using namespace std;
    5. class Solver1 {
    6.     static const int MAXN = 1000 + 10;
    7.     const int INF = 0X3f3f3f3f;
    8.     int v[MAXN], w[MAXN];
    9.     int dp[MAXN] = {};
    11. public:
    12.     void f() {
    13.         int N, V;
    14.         cin >> N >> V;
    15.         for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];
    16.         for (int i = 1; i <= N; i++) 
    17.             for (int j = v[i]; j <= V; j++)
    18.                 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    19.         cout << dp[V] << endl;
    20.     }
    22.     void f2() {
    23.         int N, V;
    24.         cin >> N >> V;
    25.         for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];
    26.         for (int i = 1; i <= N; i++)
    27.             for (int j = V; j >= v[i]; j--)
    28.                 for (int k = 0; k * v[i] <= j; k++)
    29.                     dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
    31.         cout << dp[V] << endl;
    32.     }
    34.     void f3() {
    35.         int N, V;
    36.         cin >> N >> V;
    37.         for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];
    38.         dp[0] = 0;
    39.         for (int i = 1; i <= V; i++) dp[i] = -INF;
    41.         for (int i = 1; i <= N; i++)
    42.             for (int j = v[i]; j <= V; j++)
    43.                 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    45.         cout << *max_element(dp + 1, dp + 1 + V) << endl;
    46.     }
    47. };
    49. int main() {
    50.     Solver1 s;
    51.     s.f3();
    52. }