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.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;


public class Main {
    private static int [] P;
    private static int n,k;

    private static long [] gen(int [] P,int n,int target) {
        PriorityQueue<state> PQ = new PriorityQueue<>();
        PQ.add(new state(1L,-1));

        ArrayList<Long> aux = new ArrayList<>();
        for (int q = 0;q < target && !PQ.isEmpty();q++){
            state cur = PQ.poll();
            long u = cur.value;
            int i = cur.lst;
            aux.add(u);
            if (i >= 0 && u <= Long.MAX_VALUE/P[i])
                PQ.add(new state(u*P[i],i));
            for (++i;i < n && u <= Long.MAX_VALUE/P[i];i++)
                PQ.add(new state(u*P[i], i));
        }
        target = aux.size();
        long [] g = new long[target];
        for (int i = 0;i < target;i++)
            g[i] = aux.get(i);
        return g;
    }
    private static long getCnt(long v,long [] L,long [] R) {
        int i = 0;
        while (i < R.length && R[i] <= v) i++;
        long ret = 0;
        for (long x : L) {
            while (i > 0 && (R[i-1] > v/x || x*R[i-1] > v))
                i--;
            ret += i;
        }
        return ret;
    }

    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        n = io.getNextInt();
        P = new int[n];
        for (int i = 0;i < n;i++) P[i] = io.getNextInt();
        k = io.getNextInt();
        Arrays.sort(P);
        int [] L = new int[(n+1)/2];
        int [] R = new int[n/2];
        for (int i = 0;i < n;i += 2) L[i >> 1] = P[i];
        for (int i = 1;i < n;i += 2) R[i>>1] = P[i];
        int T = 800*1000;
        long [] gL = gen(L,L.length,T),gR = gen(R,R.length,T);
//        System.err.println(Arrays.toString(gL));
//        System.err.println(Arrays.toString(gR));
        long s = 1,e = (long)1e18;
        while (s < e) {
            long m = s + (e-s)/2;
            if (getCnt(m,gL,gR) >= k) e = m;
            else s = m+1;
        }
        io.println(s);
//        System.err.println(getCnt(s,gL,gR) + " " + k);
        io.close();
    }
}

class state implements Comparable<state>{
    long value;
    int lst;
    public state(long v,int l) {
        value = v;
        lst = l;
    }
    @Override
    public int compareTo(state o) {
        long d = value - o.value;
        if (d < 0) return -1;
        if (d == 0) return lst - o.lst;
        return 1;
    }
}


class point{
    private static DecimalFormat df = new DecimalFormat("#.###");
    double x,y;
    public point(double x,double y){
        this.x = x;
        this.y = y;
    }
    point vec(point to) {
        return new point(to.x - x,to.y - y);
    }
    public double length(){
        return Math.sqrt(x*x + y*y);
    }
    @Override
    public String toString(){
        return "(" + df.format(x) + ", " + df.format(y) + ")";
    }
    double dot(point p) {
        return x*p.x + y*p.y;
    }
    double cross(point p) {
        return x*p.y - y*p.x;
    }
}


class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}