// Contoh Bab 13: knapsack 0/1, greedy dibandingkan dengan DP.
//
// Compile:  g++ -std=c++17 -O2 -o knapsack exercises/13/03-knapsack.cpp
// Jalankan: ./knapsack
// Contoh masukan: 3 10
//                 6 10
//                 5 7
//                 5 7
// (berat nilai per baris; greedy memilih barang pertama, DP memilih dua
// barang terakhir)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAKSN = 105;
const int MAKSW = 10005;

int w[MAKSN], v[MAKSN];
int dp[MAKSN][MAKSW];

struct Barang {
    int berat, nilai;
};

int greedy(int n, int W) {
    Barang b[MAKSN];
    for (int i = 1; i <= n; i++) { b[i - 1].berat = w[i]; b[i - 1].nilai = v[i]; }

    // urut menurut nilai per berat, dari yang paling untung
    sort(b, b + n, [](Barang x, Barang y) {
        return (long long)x.nilai * y.berat > (long long)y.nilai * x.berat;
    });

    int sisa = W, total = 0;
    for (int i = 0; i < n; i++) {
        if (b[i].berat <= sisa) {
            sisa -= b[i].berat;
            total += b[i].nilai;
        }
    }
    return total;
}

int main() {
    int n, W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++) {
        for (int b = 0; b <= W; b++) {
            dp[i][b] = dp[i - 1][b];
            if (b >= w[i] && dp[i - 1][b - w[i]] + v[i] > dp[i][b])
                dp[i][b] = dp[i - 1][b - w[i]] + v[i];
        }
    }

    cout << "greedy: " << greedy(n, W) << "\n";
    cout << "dp    : " << dp[n][W] << "\n";
    return 0;
}