Use Java to write

Automatic coin exchange machine $($CoinChange$)$

Automated coin exchange machines are everywhere. Especially in systems that require coins to pay for the value of things or services, users must bring the banknotes they want to exchange for coins into the automatic coin exchange machine. And the automatic coin exchange machine returns the user with different types of coins, each of which has a different value per coin. The total value of all coins is equal to the value of all banknotes imported by the user. But the number of coins of each type may not be the same. In addition, so that the automatic coin exchange machine can provide coin exchange services to customers for a long time. The automatic coin exchange machine will calculate the coins returned to the user. The important condition is that $$the total number of coins must be as small as possible.$$

Have students write a program to receive input data as follows.

$$ Total value of banknotes that the user wishes to exchange for coins $($A baht$)$

$$ Number of different types of coins. Available in automatic coin exchangers $($N type$)$

$$ Value of each type of coin $($Ci baht, $1$ i $$ N$)$

To calculate and display the total number of coins that the automatic coin exchange machine will return to the user.

Example $1$: Total value of banknotes that the user wishes to exchange for $12$ baht coins. In an automatic coin exchange machine, there are $3$ types of coins, each with a value of $1$ baht, $5$ baht, and $10$ baht.

The automatic coin exchange machine will return $3$ coins to the user with a total value of $12$ baht as follows $(1$ x $10+2$ x $1)$

Example $2$: Total value of banknotes that the user wishes to exchange for $30$ baht coins. In an automatic coin exchange machine, there are $3$ types of coins, each with a value of $1$ baht, $15$ baht, and $25$ baht.

The automatic coin exchange machine will return $2$ coins to the user, total value $30$ baht, as follows $(2$ x $15)$

input data

The input data has N$+2$ lines as follows.

Line one Consisting of one integer, specifying the value A$,$ let $1<=$ A $<=2,500$ represent the total value of banknotes that the user wishes to exchange for coins.

The second line consists of one integer specifying the value N$,$ where $3<=$ N $<=25$ represents the number of different types of coins. which is available in automatic coin exchange machines

Lines $3$ through N$+2$ each contain one integer $1<=$ Ci $<=100,1$ i $$ N representing the value of each type of coin. which is available in automatic coin exchange machines

note

Specify that every input always has the correct format, bounds, and set of possible values. Students do not need to validate their input.

Export data

The output data has one line. Displays the result as a single integer. Specifies the total number of coins that the vending machine will return to the user.

Example $1$

input data

$12$

$3$

$1$

$5$

$10$

Export data

$3$

Example $2$

input data

$30$

$3$

$15$

$1$

$25$

Export data

$2$