시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 215 43 35 24.648%

문제

이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다.

빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만드려고 한다.

1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 같지 않기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만드려고 한다.

예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이 만들 수 있는 가장 큰 수는 210(8+7+6=21)이다.
 

입력

문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파는 숫자는 0,1,2,3인 것이다. 둘째 줄에 각 숫자를 사는데 드는 비용이 작은 숫자부터 주어진다. 이 비용은 50보다 작거나 같은 자연수이다. 마지막 줄에는 백은진이 현재 가지고 있는 돈이 주어진다. 돈은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 백은진이 가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력한다. 백은진이 가지고 있는 돈은 적어도 숫자 하나는 살 수 있기 때문에, 답은 항상 존재한다.

0을 제외하고 0으로 시작하는 수는 없다.

예제 입력

3
6 7 8
21
3
5 23 24
30
10
1 1 1 1 1 1 1 1 1 1
50

예제 출력

210
20
99999999999999999999999999999999999999999999999999

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: kcm1700