양팔 저울

서로 무게가 다른 추들이 주어진다. 각 추의 무게는 1g 이상 9g 이하의 정수이다. 이 추들 중 일부를 골라 양팔 저울 위에 올려 평형을 만들고자 한다.

저울의 양쪽에는 중심에서 같은 간격으로 떨어진 눈금이 5개씩 있다. 추는 반드시 눈금 위에만 놓을 수 있으며, 한 눈금에는 추를 하나만 놓을 수 있다. 예를 들어 추 집합이 {2, 3, 4, 5, 9}일 때, 왼쪽에서 중심으로부터 거리 3인 곳에 2g 추를 놓고 오른쪽에서 중심으로부터 거리 2인 곳에 3g 추를 놓으면 2×3 = 3×2이므로 저울은 평형을 이룬다. 같은 추 집합에서 왼쪽 거리 4에 4g 추, 왼쪽 거리 2에 2g 추를 놓고 오른쪽 거리 4에 5g 추를 놓아도 4×4 + 2×2 = 5×4이므로 평형이다.

저울이 평형을 이루는 배치 하나마다 숫자 하나를 만든다. 가장 왼쪽 눈금부터 가장 오른쪽 눈금까지 차례로 읽으면서, 빈 눈금에는 0을 쓰고 추가 놓인 눈금에는 그 추의 무게를 쓴다. 그런 다음 처음으로 0이 아닌 숫자가 나오기 전의 앞쪽 0을 모두 지운다. 위의 첫 번째 배치는 20003000, 두 번째 배치는 402000050에 대응된다. 이렇게 얻은 최대 10자리의 정수를 평형정수라고 한다.

주어진 추 집합으로 만들 수 있는 모든 평형정수를 증가하는 순서로 나열했을 때, 순위 k에 해당하는 평형정수를 출력하라. 0 ≤ k ≤ 1,000,000,000이며, k = 0인 평형정수는 아무 추도 올리지 않은 상태를 뜻하는 0이다. 순위 k에 해당하는 평형정수가 없으면 만들 수 있는 가장 큰 평형정수를 출력한다.

첫째 줄에 추 집합의 크기 n이 주어진다. 1 ≤ n ≤ 9이다.

둘째 줄에는 서로 다른 n개의 추 무게가 증가하는 순서로 주어진다. 각 무게는 1 이상 9 이하의 정수이며, 인접한 두 수는 공백 하나로 구분된다.

셋째 줄에는 구해야 하는 순위 k가 주어진다.

주어진 추들로 만들 수 있는 모든 평형정수를 증가하는 순서로 나열했을 때 k번째가 되는 평형정수를 첫째 줄에 출력한다. 그런 정수가 없으면 만들 수 있는 가장 큰 평형정수를 출력한다.