import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
{
int[] coin = { 5, 10, 50, 100, 500 };
int[] pay = new int[coin.length];
int count = 0;
int countone = 0;
Loop:
for (;; pay[0]++) {
for (int i = 0; i < pay.length; i++) {
int sum = 0;
for (int j = 0; j < pay.length; j++) {
sum += coin[j] * pay[j];
}
if (sum > num) {
if (i == pay.length - 1 || coin[i] > num) break Loop;
for (int j = 0; j <= i; j++) pay[j] = 0;
pay[i + 1]++;
countone = 0;
} else {
countone = 1;
}
}
count += countone;
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUKewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCiAgICB7CgogICAgICAgIGludFtdIGNvaW4gPSB7IDUsIDEwLCA1MCwgMTAwLCA1MDAgfTsKICAgICAgICBCdWZmZXJlZFJlYWRlciBiciA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CiAgICAgICAgU3RyaW5nIGxpbmUgPSBici5yZWFkTGluZSgpOwogICAgICAgIGludCBudW0gPSBJbnRlZ2VyLnBhcnNlSW50KGxpbmUpOwoKICAgICAgICBpbnRbXSBwYXkgPSBuZXcgaW50W2NvaW4ubGVuZ3RoXTsKICAgICAgICBpbnQgY291bnQgPSAwOwogICAgICAgIGludCBjb3VudG9uZSA9IDA7CgpMb29wOgogICAgICAgIGZvciAoOzsgcGF5WzBdKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBwYXkubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgICAgIGludCBzdW0gPSAwOwogICAgICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBwYXkubGVuZ3RoOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBzdW0gKz0gY29pbltqXSAqIHBheVtqXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIChzdW0gPiBudW0pIHsKCQkJCQlpZiAoaSA9PSBwYXkubGVuZ3RoIC0gMSB8fCBjb2luW2ldID4gbnVtKSBicmVhayBMb29wOwoJCQkJCWZvciAoaW50IGogPSAwOyBqIDw9IGk7IGorKykgcGF5W2pdID0gMDsKCSAgICAgICAgICAgICAgICBwYXlbaSArIDFdKys7CgkgICAgICAgICAgICAgICAgY291bnRvbmUgPSAwOwogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIAljb3VudG9uZSA9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY291bnQgKz0gY291bnRvbmU7CiAgICAgICAgfQogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihjb3VudCk7CiAgICB9Cn0=