Minimum Number of Notes

You are given two note denominations, \(M\) and \(B\), and a target amount \(X\). Your task is to determine the minimum number of notes required to sum exactly to \(X\) using these two denominations. If it is not possible to form \(X\) with any combination of \(M\) and \(B\), output \(-1\).

For example, if \(M = 4\), \(B = 5\) and \(X = 23\), one optimal solution is to use 3 notes of \(4\) and 2 notes of \(5\) (i.e. \(3 \times 4 + 2 \times 5 = 12 + 10 = 22\)), although in this case it doesn't sum to 23; a correct combination should exactly match \(X\). Your solution should try all valid combinations to find the minimum total number of notes required.

Note: Ensure that the program reads input from STDIN and writes the result to STDOUT.

inputFormat

The input consists of a single line containing three space-separated integers \(M\), \(B\) and \(X\):

• \(M\) and \(B\) represent the two note denominations.
• \(X\) is the target amount.

outputFormat

Output a single integer representing the minimum number of notes needed to exactly form \(X\). If it is not possible to form \(X\) using the given denominations, output \(-1\).

4 5 23

5