Problem 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.

Sample Input and Output

Sample Input #1

4

Sample Output #1

4

Sample Input #2

7

Sample Output #2

11

Sample Input #3

6

Sample Output #3

14

Notes

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

见题面 Input 部分

见题面 Output 部分