Holes

Time limit3sMemory limit256 MB

Summary

Find the smallest non-negative integer without leading zeros whose digits produce exactly h holes, where 0,4,6,9 give one hole and 8 gives two.

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

Problem

You may have seen a mechanical typewriter — such devices were widespread only a few decades ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter molded into the type bar strikes the paper. The art of typewriter typing, however, is more complicated than the art of computer typing: you should strike the keys with some force, otherwise the prints will not be dark enough; but you should not overdo it, otherwise the paper will be damaged.

Imagine a typewriter with very sharp letters, which cut the paper instead of printing on it. When the digit 0 is typed on such a typewriter, it makes a nice hole in the paper (and you receive a small paper oval as a bonus). The same happens with some other digits: 4, 6, and 9 each produce one hole, and 8 produces two touching holes. The remaining digits (1, 2, 3, 5, 7) just cut the paper without making any holes.

You want to make an art installation consisting of an empty sheet of paper with exactly h holes, made by typing a single non-negative integer on the cutting typewriter described above. Among all numbers that produce exactly h holes, the number must be the smallest possible, and it must not have leading zeroes. Write a program that generates the required number.

Input

A single integer h (0 ≤ h ≤ 510) — the number of holes.

Output

Print the number that must be typed.

Examples4

Example 1
Input
```
0
```
Expected output
```
1
```
Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
15
```
Expected output
```
48888888
```
Example 4
Input
```
70
```
Expected output
```
88888888888888888888888888888888888
```