Optimal Coin Change

Given a set of coin denominations and a target amount, write a program to determine the minimum number of coins needed to make that amount. If it cannot be made with the coins you have, print -1. The program should read from STDIN and print the minimum number of coins to STDOUT. Input format: First line contains an integer n (1 <= n <= 50) followed by n integers representing the coin denominations. The last line contains an integer amount (1 <= amount <= 10^6). Output format: A single integer, the minimum number of coins needed, or -1 if it is not possible. Example: Input: 3 1 2 5 11 Output: 3