SMILEY1807 - 1807

There is a SmileyLand of angels. The queen of all angels Smiley1807 loves the number 1807. She is so much obsessed with 1807 that she asked her programmer friend to write a program to find the length of the largest sub sequence having digits 1, 8, 0 and 7 in order. For example if given sequence is 1800777700088888000777 then one of the largest sub sequence satisfying the above condition is 1800000000777 (there is one more possibility of 1888888000777) and hence the length of largest sub sequence is 13.

Input

The input contains only one test case.

The test case consist of only one sequence which may be as long as 10^6. There are only 1, 8, 0 or 7 present in the input sequence.

Output

Output contains only one line containing the length of the largest sub-sequence.

Example

Input:
1800777700088888000777

Output:
13

Explanation

1800000000777 is the largest sub-sequence


Added by:Amitayush Thakur
Date:2015-08-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:MAWK BC C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 C99 COFFEE LISP sbcl LISP clisp DART FORTH HASK JAVA JULIA KTLN OCT PROLOG PYTHON PYPY3 PYTHON3 PY_NBC R RACKET SCALA SQLITE SWIFT UNLAMBDA
Resource:Own problem made for college competition CodeNite-1

hide comments
2016-04-15 04:16:13 eti goel
what is expected time complexity ?
2016-01-19 10:44:54 Arjav Patel
why am i getting SIGSEGV error?
2015-12-06 20:45:01 SUBHAJIT GORAI
nice question ....think simple ....
2015-12-06 18:35:18 Jacob Plachta
If there are no valid subsequences, the expected output is "0".
2015-09-17 20:46:56 Amitayush Thakur
@biswas: It is not giving WA. It is giving Runtime error. Try to understand why the runtime error is there.
2015-09-17 20:42:49 Amitayush Thakur
Solution id=15055783(Aplav Garg) and id=15055752(vishu) disqualified for copying.

Last edit: 2015-09-17 20:49:18
2015-09-02 16:35:52 biswas
My ID is 15048369... Giving WA. Don't Know why. Please help.
2015-09-01 16:30:34 poojan
what is ans for 1870? 3 or 0?

edit : finally done .
test case: 1870007000700 ans 9
181108118807 ans 9




Last edit: 2015-09-03 11:58:55
2015-08-30 18:48:07 Arjav
Enjoyed the chase!!!!!
2015-08-30 10:23:46 Sagnik Mondal
Got AC . thnks :)

(Reply)
Try using scanf("%s") rather than scaning char by char and increase the size of your array

Last edit: 2015-08-31 18:06:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.