577. King's Gold Coin Reward

0

Medium

King Andrew, the ruler of a kingdom, rewards people with gold coins for their good deeds. He wants to reward them with the fewest number of coins possible. However, his smartest minister, Drake, is currently unavailable. Therefore, you have been tasked with helping the king in this endeavor. You are given an array called 'coins' which represents different denominations of coins, and an integer called 'amount' which represents the total amount of money to be rewarded. Your task is to determine the fewest number of coins needed to make up the given amount. If it is not possible to make up the amount using any combination of the coins, you should print -1. You can assume that you have an infinite number of each kind of coin.

Input Format

The first line contains the size of the array. The second line contains the elements of the array. The third line contains the target amount.

Output Format

Print the fewest number of coins required to reach the target value.

Example

Input

3 1 2 5 11

Output

3

Constraints

1 <= arr.length <= 12
1 <= arr[i] <= 231 - 1
0 <= amount <= 104