Problem J. Jubilees ≡

 Author: A. Klenin Input file: input.txt Time limit: 1 sec Output file: output.txt Memory limit: 256 Mb

Statement

Let's define that a positive integer is a jubilee if it is divisible by 5 and is no less than 10. (i.e. 10, 15, 20, …).

Your program must, given a sequence of N decimal digits, find maximum number of jubilees which can be made by splitting this sequence into disjoint subsequences. In other words, every digit of sequence must be used no more than once and original order of digits must be preserved.

In the first sample, sequence 2535 can be split into 25 and 35.

In the second sample, sequence 1115005000 can be split into 10, 10, 10, 50 and 50.

Input file format

Input file contains a string of N decimal digits. First digit is non-zero.

Output file format

Output file must contain a single integer — number of jubilees.

1 ≤ N ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2535
2
2
1115005000
5

0.485s 0.005s 9