Super-Duper-ATM

Banknotes in circulation come in denominations of 1, 2, 5, 10, 20, 50, 100, 200, and 500 hryvnias. The Super-Duper-ATM has an ample supply of each denomination. Your task is to determine the minimum number of banknotes the ATM can dispense to total the amount S.

Input Data

A single integer S, where 1 ≤ S ≤ 12345.

Output Data

A single integer representing the minimum number of banknotes needed to dispense the specified amount.

Examples

Note

For example, the amount 2018 can be dispensed using 500+500+500+500+10+5+2+1, totaling eight banknotes. It is not possible to dispense the amount 2018 with fewer banknotes using the available denominations.