1084번 - 방 번호 2

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 P_i이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P₀ = 6, P₁ = 7, P₂ = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

첫째 줄에 N이 주어진다. 둘째 줄에는 공백으로 구분된 P₀, ..., P_N-1이 주어진다. 마지막 줄에는 M이 주어진다.

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호의 자릿수를 출력한다. 가장 큰 방 번호를 X라고 했을 때, 둘째 줄에는 X의 처음 50자리를 출력하고, 셋째 줄에는 마지막 50자리를 출력한다. 만약, X의 자릿수가 50보다 작은 경우 둘째 줄과 셋째 줄에는 X를 출력한다. 만약, M원을 모두 사용해서 방 번호를 만들 수 없는 경우에는 첫째 줄에 0을 출력하고, 둘째 줄과 셋째 줄에는 아무것도 출력하지 않아야 한다.

• 1 ≤ N ≤ 10
• 1 ≤ P_i ≤ 10¹⁸
• 0 ≤ M ≤ 10¹⁸
• N, P_i, M은 정수