dp_coins_tc_1.cpp

/* Coin Change - Version II */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000
int arr[MAX], n;
int dp[MAX];

int f(int tot)
{
    if(tot == 0) return 0;
    if(dp[tot] != -1) return dp[tot];
    int mins = INT_MAX-1;
    for(int i=0; i<n; i++){
        if(tot - arr[i] >= 0) mins = min(mins, f(tot - arr[i]));
    }
    return dp[tot] = mins + 1;
}


int main()
{
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    int tot;
    scanf("%d", &tot);
    if(f(tot) == INT_MAX) cout << "not possible";
    else cout << f(tot);
}