최대 번호판

문제

새로 지은 건물에는 번호판을 직접 만들어 달아야 한다. 번호판은 0부터 N-1까지의 숫자로 구성되며, 각 숫자 i를 하나 사는 가격은 P_i원이다. 같은 숫자를 여러 번 구매할 수 있다.

준비한 예산은 M원이다. 번호판이 0으로만 이루어진 것이 아니라면, 즉 다른 숫자가 하나라도 포함되어 있다면 0으로 시작할 수 없다. 예산 내에서 만들 수 있는 가장 큰 번호판의 번호를 구하라.

두 수를 비교할 때, 자릿수가 더 많은 수가 항상 더 크며, 자릿수가 같다면 가장 높은 자리부터 순서대로 비교하여 더 큰 숫자가 있는 수가 더 크다.

입력

첫째 줄에 숫자의 종류 수 N이 주어진다.
둘째 줄에 각 숫자의 가격 P_0, ..., P_{N-1}이 공백으로 구분되어 주어진다.
셋째 줄에 예산 M이 주어진다.

출력

예산 M원 이내로 만들 수 있는 가장 큰 번호를 출력한다.

제한

• 1 ≤ N ≤ 10
• 1 ≤ P_i ≤ 50
• 1 ≤ M ≤ 50
• M원으로 적어도 하나의 숫자는 살 수 있는 입력만 주어진다.
• 번호판에 아무 숫자도 없는 경우(빈 문자열)는 고려하지 않는다.

입출력 예시

입력 1

3
6 7 8
21

출력 1

210

입력 2

3
5 23 24
30

출력 2

20

입력 3

4
1 5 3 2
1

출력 3

0

입력 4

10
1 1 1 1 1 1 1 1 1 1
50

출력 4

99999999999999999999999999999999999999999999999999