E. Простой подарок
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
— Мужик, у тебя простые числа есть?

— Нету.

— На, мужик, простые числа.

Пингвин

В отличие от Гриши, который вел себя хорошо, Олег за весь год так и не научился решать задачи на теорию чисел. Поэтому вместо Деда Мороза к нему пришел его сокомандник Андрей и торжественно вручил ему множество из n различных простых чисел вместе с простой задачей: Олегу необходимо найти k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из этого множества.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 16) — количество чисел во множестве.

Во второй строке n различных простых чисел p1, p2, ..., pn (2 ≤ pi ≤ 100) — числа во множестве. Гарантируется, что числа идут в порядке возрастания.

В третьей строке задано число k (1 ≤ k). Гарантируется, что k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из данного множества не превосходит 1018.

Выходные данные

Выведите k-е в порядке возрастания число, удовлетворяющее условию. Гарантируется, что оно не превосходит 1018.

Примеры
Входные данные
3
2 3 5
7
Выходные данные
8
Входные данные
5
3 7 11 13 31
17
Выходные данные
93
Примечание

Для первого примера последовательность с простыми делителями из набора {2, 3, 5} выглядит так:

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

Седьмым по счету числом (в 1-индексации) как раз и будет восьмерка.