Fewest notes for a payment

Problem

A cashier has unlimited notes of values 1, 2, 5, 10, 20, 50 and 100. Given an amount, print the smallest number of notes that add up to it.

Example 1

Input

Output

Example 2

Input

Output

Try the problem first. Open one hint at a time.

Hint 1

These note values let the largest note first rule work.

Hint 2

For each note from largest to smallest, add amount // note and keep amount % note.

Write your Python code, run it on the examples and submit it to hidden tests.