Prime Gift

Grisha의 훌륭한 행동과는 반대로, Oleg는 일 년이라는 시간이 온전히 주어졌음에도 지난 한 해 동안 정수론 문제를 푸는 법을 익히지 못했다. 그래서 Ded Moroz 대신 그의 팀 동료 Andrew가 찾아와, 서로 다른 소수 n개로 이루어진 집합과 함께 간단한 과제를 엄숙히 건넸다. Oleg는 모든 소인수가 이 집합에 속하는 정수 중 k-th번째로 작은 정수를 찾아야 한다.

첫째 줄에 정수 하나 n (1 ≤ n ≤ 16)이 주어진다.

다음 줄에는 서로 다른 소수 n개 p1, p2, ..., pn (2 ≤ pi ≤ 100)이 오름차순으로 주어진다.

마지막 줄에 정수 하나 k (1 ≤ k)이 주어진다. 모든 소인수가 이 집합에 속하는 정수 중 k-th번째로 작은 정수가 1018을 초과하지 않음이 보장된다.

k-th번째로 작은 정수를 한 줄에 출력한다. 답이 1018을 초과하지 않음이 보장된다.

모든 소인수가 {2, 3, 5}에 속하는 수의 목록은 다음과 같이 시작한다:

(1, 2, 3, 4, 5, 6, 8, ...)

이 목록에서 일곱 번째 수(1부터 세었을 때)는 여덟이다.