Problem: Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of n distinct prime numbers alongside with a simple task: Oleg is to find the k-th smallest integer, such that all its prime divisors are in this set. 

Input

The first line contains a single integer n (1 ≤ n ≤ 16).

The next line lists n distinct prime numbers p1, p2, ..., pn (2 ≤ pi ≤ 100) in ascending order.

The last line gives a single integer k (1 ≤ k). It is guaranteed that the k-th smallest integer such that all its prime divisors are in this set does not exceed 1018.

Output

Print a single line featuring the k-th smallest integer. It's guaranteed that the answer doesn't exceed 1018.

Examples

Input

3
2 3 5
7


Output

8


Input

5
3 7 11 13 31
17


Output

93

Note

The list of numbers with all prime divisors inside {2, 3, 5} begins as follows:

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

The seventh number in this list (1-indexed) is eight.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) {
        InputStream  inputStream  = System.in;
        OutputStream outputStream = System.out;
        InputReader in   =  new InputReader(inputStream);
        PrintWriter out  =  new PrintWriter(outputStream);
        Solver solver    =  new Solver(in, out);
        solver.solve();
        out.close();
    }

    static class ArrayList{
        long num[] = new long[(int)6e6];
        int size = 0;
        void add(long x) {
            num[size++] = x;
        }
        int size() {
            return size;
        }

        long get(int i) {
            return num[i];
        }


    }

    static class Solver {
        private InputReader in;
        private PrintWriter out;
        private StringBuilder   answer  =   null;
        private final String    blank   =   " ";
        private final long Max = (long)(1e18);
        private ArrayList list1 = new ArrayList();
        private ArrayList list2 = new ArrayList();
        private ArrayList set1 = new ArrayList();
        private ArrayList set2 = new ArrayList();

        void preCal(ArrayList list, int k, long bound, long add, ArrayList set) {
            if(k >= list.size()) {
                set.add(add);
                return;
            }
            while(bound>0) {
                preCal(list, k+1, bound, add, set);
                long tmp = list.get(k);
                add *= tmp;
                bound /= tmp;
            }
        }

        long cal(long tmp) {
            long res = 0;
            int yidx = 0;
            for(int i = 0; i < set1.size(); ++i){
                long x = set1.get(i);
                while (yidx < set2.size() && set2.get(yidx) <= tmp / x) {
                    yidx++;
                }
                res += yidx;
            }
            return res;
        }

        void solve() {
            int n = in.nextInt();
            for(int i = 0; i < n; ++i) {
                if(i%2 == 0) list1.add(in.nextLong());
                else list2.add(in.nextLong());
            }
            long k = in.nextLong();
            preCal(list1, 0, Max, 1, set1);
            preCal(list2, 0, Max, 1, set2);
            Arrays.sort(set1.num, 0, set1.size());
            Arrays.sort(set2.num, 0, set2.size());
            long num[] = new long[set1.size()];
            for(int i = 0; i < num.length; ++i) {
                num[i] = set1.get(num.length-i-1);
            }
            set1.num = num;
            long l = 0;
            long r = Max+1;
            while (l != r) {
                long m = (l+r) / 2;
                if (cal(m)<k) l = m + 1;
                else r = m;
            }
            if (l!=Max+ 1) out.print(l);
            else out.print(-1);
        }
        Solver(InputReader i, PrintWriter o) {in = i; out = o; }
    }
    static class InputReader {
        private BufferedReader  br;
        private StringTokenizer tokenizer = null;
        InputReader(InputStream stream) { br = new BufferedReader(new InputStreamReader(stream));}
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try { tokenizer = new StringTokenizer(br.readLine());}
                catch (IOException e) { throw new RuntimeException();}
            }
            return tokenizer.nextToken();
        }
        int     nextInt()   { return Integer.parseInt(next());}
        long    nextLong()  { return Long.parseLong(next());}
        double  nextDouble(){ return Double.parseDouble(next());}
    }
}