Auxiliary Project

Time limit3sMemory limit512 MB

Summary

Choose any multiset of digits whose total lit segments equals n, and maximize the sum of the digits.

Level: Medium4 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

Anna has just finished her course project. She has many leftover seven-segment LED displays and one small power source. A display draws power in proportion to the number of lit segments, so a 9 draws twice as much power as a 7.

One display shows one digit from 0 to 9, and the number of segments each digit lights is fixed.

Digit	0	1	2	3	4	5	6	7	8	9
Segments	6	2	5	5	4	5	6	3	7	6

Anna may use as many displays as she likes, and she wants exactly $n$ segments lit in total. Find the largest possible sum of the digits she displays.

Input

The only line contains one integer $n$ , the number of segments that must be lit. ( $2 \le n \le 10^6$ )

Output

Print one integer, the largest possible sum of digits displayed at the same time.

Note

For $n = 4$ a single 4 is displayed. A 7 is worth more but lights only three segments, so the fourth segment would go unused. For $n = 7$ the displays show 4 and 7, and for $n = 6$ they show two 7s.

Examples3

Example 1
Input
```
4
```
Expected output
```
4
```
Example 2
Input
```
7
```
Expected output
```
11
```
Example 3
Input
```
6
```
Expected output
```
14
```