Largest Room Number 2

Time limit2sMemory limit128 MB

Summary

Given per-digit purchase costs and a budget, find the largest number (no leading zero) affordable, then output its length and its first and last 50 digits.

Level: Medium7 of 10
Topics: Greedy, Math, Simulation, String
Solved: No attempts yet

Problem

You want to choose a room number for an office. To form the number, you must buy digit cards, and you can spend at most M won.

The available digit cards are 0 through N-1, and digit i costs P_i won. You may buy the same digit multiple times, and there is always enough stock. If the room number is not 0, it may not start with 0.

Find the largest room number X that can be made using at most M won. Since X can be very long, print its length and only the front and back parts of the number.

Input

The first line contains the number of digits N.

The second line contains P_0, P_1, ..., P_{N-1}, separated by spaces.

The third line contains the available budget M.

Output

On the first line, print the number of digits in the largest room number X.

On the second line, print the first 50 digits of X. On the third line, print the last 50 digits of X. If X has fewer than 50 digits, print X on both the second and third lines.

If no room number can be made, print 0 on the first line and leave the second and third lines empty.

Constraints

1 <= N <= 10
1 <= P_i <= 10^18
0 <= M <= 10^18
N, P_i, and M are integers.

Examples8

Example 1
Input
```
3
6 7 8
21
```
Expected output
```
3
210
210
```

Example 2

Input

3
1 7 8
21

Expected output

15
100000000000000
100000000000000

Example 3

Input

10
1 1 1 1 1 1 1 1 1 1
923372036854775807

Expected output

923372036854775807
99999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999

Example 4

Input

2
1 923372036854775807
923372036854775807

Expected output

1
1
1

Example 5

Input

2
1 923372036854775806
923372036854775807

Expected output

2
10
10

Example 6
Input
```
3
1 5 10
10
```
Expected output
```
6
100000
100000
```

Example 7

Input

2
1 923372036854775807
923372036854775806

Expected output

1
0
0

Example 8

Input

2
1 10
1000000

Expected output

999991
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000