## TCCC '24 Apr P5 - Perfect Measurements

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

Thornhill Computer Club 2024 - April Contest - Problem 5

krem is baking a large cake that requires cups of flour. However, all the markings on his measurement devices have been erased, leaving him unable to measure precise amounts of flour. Luckily, krem knows the th measuring device can hold cups of flour when completely filled. Instead of buying new measuring devices, krem wants to know if he can measure exactly cups of flour using his measuring devices. Can you determine the minimum number of times krem needs to measure out flour only using his measuring devices before he has exactly cups? If it is impossible to do so, output -1.

#### Input Specification

The first line will contain two integers and , the number of cups of flour and number of measuring devices.
The next line will contain integers , the number of cups of flour the th measuring device can hold.

#### Output Specification

Output a single integer, the minimum number of times krem needs to measure out flour. Output -1 if it is impossible.

100 3
33 40 1

4

#### Explanation for Sample Output 1

krem can measure out 33 cups of flour three times and 1 cup of flour one time.

12 4
1 2 3 4

3

#### Explanation for Sample Output 2

krem can measure out 4 cups of flour three times.

203 3
16 33 54

-1

#### Explanation for Sample Output 3

It is impossible for krem to measure out exactly 18 cups of flour using measurement devices of 16, 33, and 54.