Решта

Limits: 2 sec., 256 MiB

Ні для кого не секрет, що Марічка для Зеника є сенсом його життя. Він заради неї ладен на все й нічого не пошкодує для того, щоб Марічка була щасливою.

Одного разу Зеник вирішив придбати Марічці дороге намисто в розкішному магазині в самі-сінькому центрі Львова. Біля каси він гонорово витягнув купюру вартістю 500 гривень. Продавець має багато купюр таких вартостей: 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень. Він дасть Зеникові решту таким чином, щоб використати якомога меншу кількість купюр. Намисто коштує \(n\) гривень.

Вам необхідно визначити, яку кількість купюр отримає Зеник від продавця.

Input

Єдиний рядок містить ціле число \(n\) — ціну намиста в гривнях.

Output

У єдиному рядку виведіть ціле число — кількість купюр, що отримає Зеник.

Constraints

\(1 \le n \le 500\).

Samples

Input (stdin) сopy	Output (stdout) сopy
47	5

Notes

Продавець дасть решту Зеникові таким чином: дві купюри по 200 гривень та по одній купюрі 50, 2 та 1 гривню.