// Contoh Bab 13: DP koin paling sedikit -- soal yang membuat greedy gagal.
//
// Compile:  g++ -std=c++17 -O2 -o koindp exercises/13/02-koin.cpp
// Jalankan: ./koindp
// Contoh masukan: 3 6
//                 1 3 4

#include <iostream>
using namespace std;

const int BESAR = 1000000000;
const int MAKS = 1000005;
int dp[MAKS];
int c[20];

int greedy(int k, int m) {
    int jumlah = 0;
    for (int i = m - 1; i >= 0; i--) {     // c terurut naik, jadi mundur
        jumlah += k / c[i];
        k %= c[i];
    }
    return (k == 0) ? jumlah : -1;
}

int main() {
    int m, k;
    cin >> m >> k;
    for (int i = 0; i < m; i++) cin >> c[i];

    dp[0] = 0;
    for (int v = 1; v <= k; v++) {
        dp[v] = BESAR;
        for (int i = 0; i < m; i++) {
            if (v >= c[i] && dp[v - c[i]] + 1 < dp[v])
                dp[v] = dp[v - c[i]] + 1;
        }
    }

    cout << "greedy: " << greedy(k, m) << "\n";
    cout << "dp    : " << (dp[k] >= BESAR ? -1 : dp[k]) << "\n";
    return 0;
}