include <bits/stdc++.h>

using namespace std;

int main() { int n; cout << "Enter number of coin denominations: "; cin >> n;

vector<int> coins(n);
cout << "Enter the coin denominations: ";
for (int i = 0; i < n; i++) cin >> coins[i];

int amount;
cout << "Enter the target amount: ";
cin >> amount;

// Sort coins in descending order for greedy selection
sort(coins.rbegin(), coins.rend());

vector<int> result;
int remaining = amount;

for (int i = 0; i < n && remaining > 0; i++) {
    while (coins[i] <= remaining) {
        remaining -= coins[i];
        result.push_back(coins[i]);
    }
}

if (remaining != 0) {
    cout << "Greedy approach could not form the exact amount ";
    cout << "(this coin system may not be canonical).\n";
} else {
    cout << "Number of coins used: " << result.size() << "\n";
    cout << "Coins used: ";
    for (int c : result) cout << c << " ";
    cout << "\n";
}

return 0;

}