Largest Room Number 2

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.

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.

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.

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