CT38918

The Opal vaults of Lothar

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the moonlit lagoon of Selene, Lothar studies rows of vaults entries. One clean number will settle the guild's oldest argument. 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 <= 4000; 1 <= n <= 50; 1 <= coin <= 10^4.

Example 1:

Input: 1860 24 748 1339 1814 2077 2291 2633 3171 3189 3417 3658 3722 3901 3912 4310 4904 5154 6491 7109 7350 7449 7859 8425 9758 9926
Output: -1

Example 2:

Input: 525 24 1 735 853 877 1078 1224 1269 1422 1530 3216 3706 3727 3774 3788 3908 4884 5092 5110 5907 7650 7680 7972 9009 9399
Output: 525

Example 3:

Input: 75 24 436 711 873 1286 1294 1336 1461 2854 2866 3355 3864 4179 4200 4432 5725 5815 5886 6861 7474 8426 8584 9283 9647 9700
Output: -1

Constraints:

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

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