Coin Change

Lab Java Advanced 30 points

Read coin values and an amount (≤ 10000). Print the fewest coins needed, or -1.

Input

k, the k coin values, then the amount.

Output

One integer.

Example

Input

3
1 2 5
11

Output

Sample input available Sample output available

Editor

Java

Hints

best[v] = 1 + min(best[v - c]) over all coins c.

Solution explanation

Dynamic programming builds answers for every smaller amount and reuses them.

Show solution

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[] coins = new int[k];
        for (int i = 0; i < k; i++) coins[i] = sc.nextInt();
        int amount = sc.nextInt();
        int[] best = new int[amount + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;
        for (int v = 1; v <= amount; v++) {
            for (int c : coins) {
                if (c <= v && best[v - c] != Integer.MAX_VALUE) {
                    best[v] = Math.min(best[v], best[v - c] + 1);
                }
            }
        }
        System.out.println(best[amount] == Integer.MAX_VALUE ? -1 : best[amount]);
    }
}

Output

Answer