Under construction

Still being built. Things may change

Room Number

Interview

Time limit2sMemory limit128 MB

Summary
Given digit prices and a budget, find the largest possible room number (no leading zero unless it's just 0) that can be bought within the budget.
Level

Medium4 of 10

Topics
Greedy, String, Implementation
Solved
No attempts yet

Problem

You want to choose the room number for a new office. To make the room number, you must buy digit plates, and you have M won available.

The digits for sale are 0 through N-1, and digit i costs P_i. You may buy the same digit multiple times, and there is always enough stock.

If the room number is not 0, its first digit cannot be 0. Find the largest room number that can be made using at most M won.

Input

The first line contains N.

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

The third line contains M.

Output

Print the largest room number that can be made using at most M won.

The input always allows buying at least one digit.

Constraints

  • 1 <= N <= 10
  • 1 <= P_i <= 50
  • 1 <= M <= 50
  • N, P_i, and M are integers.

Examples4

  1. Example 1

    Input
    3
6 7 8
21
    Expected output
    210

  2. Example 2

    Input
    3
5 23 24
30
    Expected output
    20

  3. Example 3

    Input
    4
1 5 3 2
1
    Expected output
    0

  4. Example 4

    Input
    10
1 1 1 1 1 1 1 1 1 1
50
    Expected output
    99999999999999999999999999999999999999999999999999