CT36325

The Polished Exact Tender

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the lily shoals of Padmore opens only for a perfect tally of stairwells. Jace means to find out. Task: Coins of n given sizes may be used without limit. Print the minimum number of coins summing exactly to amount, or -1. Input format: First line: amount and n. Second line: n distinct coin sizes. Output format: Print the minimum coin count, or -1. Constraints: 0 <= amount <= 10000; 1 <= n <= 50; 1 <= coin <= 10^4.

Example 1:

Input: 7765 14 1914 2828 2914 3219 3953 4378 4857 5201 5274 6294 8064 9002 9492 9806
Output: -1

Example 2:

Input: 2458 14 1 1463 1970 3460 4708 4748 5283 6330 6484 8117 8170 8321 9558 9798
Output: 489

Example 3:

Input: 1137 14 1096 1149 3947 4238 4553 4736 6417 7251 7640 7917 7947 8733 9012 9495
Output: -1

Constraints:

0 <= amount <= 10000; 1 <= n <= 50; 1 <= coin <= 10^4.

Loading...
Test Cases:No test cases
No test cases available.