Maximum Sum on Seven‐Segment Displays

Anna has just finished her course project and now has a lot of seven‐segment LED displays left over along with a small power source. Each display consumes power that is proportional to the number of lit segments. For example, the digit $\displaystyle 9$ uses 6 segments while $\displaystyle 7$ uses 3 segments, meaning that $9$ consumes twice as much power as $7$.

Given a power source that can light exactly $n$ segments, Anna wants to know: what is the maximum possible sum of digits she can achieve by lighting exactly $n$ segments out of these available displays? Each digit from $0$ to $9$ has a fixed segment cost as follows:

• $0$: $6$ segments
• $1$: $2$ segments
• $2$: $5$ segments
• $3$: $5$ segments
• $4$: $4$ segments
• $5$: $5$ segments
• $6$: $6$ segments
• $7$: $3$ segments
• $8$: $7$ segments
• $9$: $6$ segments

You are to determine the maximum sum of the digits selected such that the total number of segments lit is exactly $n$. You may use as many displays as you like. Note that the displays are independent, so there is no issue with leading zeroes or forming an actual number.

Input Constraints: It is guaranteed that $n$ is an integer and $n \geq 2$, since the minimum segments required to display any digit is $2$ (for digit $1$).

inputFormat

The input consists of a single integer $n$, which represents the total number of segments that must be lit.

outputFormat

Output the maximum possible sum of digits that can be achieved by lighting exactly $n$ segments.

sample

2

1