cho.sh

Room Number

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.

Medium4GreedyStringImplementationInterviewNo attempts yetTime limit2sMemory limit128 MB

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.