가장 큰 방 번호 2

어떤 사무실의 방 번호를 정하려고 한다. 방 번호를 만들려면 숫자판을 구매해야 하며, 사용할 수 있는 금액은 M원이다.

숫자판에는 0부터 N-1까지의 숫자가 있고, 숫자 i의 가격은 P_i원이다. 같은 숫자는 여러 번 구매할 수 있으며, 필요한 만큼 항상 구매할 수 있다. 방 번호가 0이 아니라면 첫 자리에 0을 놓을 수 없다.

M원 이하를 사용해서 만들 수 있는 가장 큰 방 번호 X를 구한다. X가 매우 길 수 있으므로, 전체 문자열 대신 자릿수와 앞쪽/뒤쪽 일부만 출력한다.

첫째 줄에 숫자의 개수 N이 주어진다.

둘째 줄에 P_0, P_1, ..., P_{N-1}이 공백으로 구분되어 주어진다.

셋째 줄에 사용할 수 있는 금액 M이 주어진다.

첫째 줄에 만들 수 있는 가장 큰 방 번호 X의 자릿수를 출력한다.

둘째 줄에는 X의 처음 50자리를 출력하고, 셋째 줄에는 X의 마지막 50자리를 출력한다. X의 자릿수가 50보다 작으면 둘째 줄과 셋째 줄에 모두 X를 출력한다.

어떤 방 번호도 만들 수 없다면 첫째 줄에 0을 출력하고, 둘째 줄과 셋째 줄은 빈 줄로 출력한다.