시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 117 11 10 12.346%

문제

이번에 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인 것이다. 둘째 줄에 숫자 0을 사는 비용, 숫자 1을 사는 비용, … 숫자 N-1을 사는 비용이 차례대로 주어진다. 이 비용은 10^18보다 작거나 같다. 마지막 줄에는 백은진이 현재 가지고 있는 돈이 주어진다. 돈은 10^18보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 백은진이 가지고 있는 돈으로 만들 수 있는 가장 큰 수의 자리수를 출력한다. 둘째 줄에는 그 수의 처음 50자리를 출력하고, 셋째 줄에는 그 수의 마지막 50자리를 출력한다.

예제 입력

3
6 7 8
21
3
1 7 8
21
10
1 1 1 1 1 1 1 1 1 1
923372036854775807

예제 출력

3
210
210
15
100000000000000
100000000000000
923372036854775807
99999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999

힌트

출처