Minimum Number of Coins

You are given a cost n (in cents) and the available coin denominations are \(\{25, 10, 5, 1\}\). Your task is to determine the minimum number of coins needed to pay exactly \(n\) cents. If the cost is negative, output \(-1\) to indicate an invalid input.

Note: It is always possible to make change for any non-negative integer n since a 1-cent coin is available.

Example:

• For n = 31, the answer is 3 because \(31 = 25 + 5 + 1\).
• For n = 3, the answer is 3 (\(3 = 1+1+1\)).
• For n = 52, the answer is 4 (\(52 = 25+25+1+1\)).

inputFormat

The input consists of a single integer n (-10⁹ ≤ n ≤ 10⁹) representing the cost in cents. The input is provided via standard input (stdin).

outputFormat

Output a single integer representing the minimum number of coins required to pay exactly n cents, or -1 if the input is invalid (i.e., if n is negative). The output should be printed to standard output (stdout).

31

3