Making a Number

Interview

Time limit2sMemory limit128 MB

Summary

Given how many cards exist for each digit 0-9, build the largest possible number using some or all cards so that no two adjacent digits match and no leading zero appears.

Level: Medium6 of 10
Topics: Greedy, String, Heap
Solved: No attempts yet

Problem

Sejun has digit cards numbered from 0 through 9. Each card contains one digit, and he may choose some or all of the given cards to make one number.

The number must not start with 0, and no two adjacent digits may be the same. If only 0 can be made, the one-digit number 0 is allowed.

Given how many cards Sejun has for each digit, find the largest number that can be made while satisfying these rules.

Input

The first line contains 10 integers: the number of cards for digits 0 through 9, in order. The total number of cards is at least 1 and at most 50.

Output

Print the largest number that can be made while satisfying the rules.

Examples4

Example 1
Input
```
0 1 4 4 1 4 0 2 2 0
```
Expected output
```
878754535352323212
```
Example 2
Input
```
3 0 0 0 0 0 0 0 0 0
```
Expected output
```
0
```
Example 3
Input
```
4 1 2 0 0 0 0 0 0 0
```
Expected output
```
202010
```
Example 4
Input
```
4 1 8 0 0 0 0 0 0 0
```
Expected output
```
21202020202
```