Description

Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g . $‘9'$ consumes twice more power than $‘7'.$

Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light $n$ segments, and she wants to light exactly $n$ segments.

Input Format

The single line of the input contains one integer $n$ -- the number of segments that should be lit $(2 \le n \le 10^{6}).$

Output Format

Output a single integer -- the maximum possible sum of digits that can be displayed simultaneously.

4

4

7

11

6

14

Hint

Time limit: 3 s, Memory limit: 512 MB.