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;

vector<int> dp(amount + 1, INT_MAX);
vector<int> lastCoin(amount + 1, -1);
dp[0] = 0;

for (int i = 1; i <= amount; i++) {
    for (int j = 0; j < n; j++) {
        if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
            if (dp[i - coins[j]] + 1 < dp[i]) {
                dp[i] = dp[i - coins[j]] + 1;
                lastCoin[i] = coins[j];
            }
        }
    }
}

if (dp[amount] == INT_MAX) {
    cout << "It is not possible to form the amount with given coins.\n";
} else {
    cout << "Minimum number of coins required: " << dp[amount] << "\n";
    // Reconstruct the coins used
    vector<int> used;
    int cur = amount;
    while (cur > 0) {
        used.push_back(lastCoin[cur]);
        cur -= lastCoin[cur];
    }
    cout << "Coins used: ";
    for (int c : used) cout << c << " ";
    cout << "\n";
}

return 0;

}