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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;


public final class CF_456_E{

	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static long mod=1000000007;



	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static long MX=1000000000000000001L;

	//static long MX=1000000000000000001L;
	static long max=0;
	static long k;

	static boolean stop;

	// count number of combination that is <=x
	static long count(long x,int[] p,int pos,long base){
		if (stop)
			return k+1;
		max=Math.max(max,base);
		long res=0;
		if (pos<0)
			return 1;
		long b=base;
		loop:while (b<=x){
			res+=count(x,p,pos-1,b);
			if (res>k) {
				stop=true;
				return k+1;

			}
			if (b<=x/p[pos])
				b*=p[pos];
			else break loop;

		}
		return res;
	}



	static ArrayList<Long>[] generate(int[] p){
		ArrayList<Long>[] res=new ArrayList[2];
		res[0]=new ArrayList<Long>();
		res[1]=new ArrayList<Long>();
		res[0].add(1L);
		res[1].add(1L);
		
		for (int i=0;i<p.length;i++){
			long x=p[i];
			ArrayList<Long> lst;
			if (res[0].size()>res[1].size())
				lst=res[1];
			else
				lst=res[0];
			int L=lst.size();
			ArrayList<Long> pow=new ArrayList<Long>();
			
			lp:while (true){
				pow.add(x);
				if (x<=MX/p[i])
					x*=p[i];
				else
					break lp;
			}
			for (int j=0;j<L;j++){
				long y=lst.get(j);
				lp:for (long xx:pow){
					if (y<=MX/xx)
						lst.add(y*xx);
					else
						break lp;
				}
			}

		}
		return res;
	}

	static ArrayList<Long> generate(int[] p,int e){
		//log("------------");
		ArrayList<Long> lst=new ArrayList<Long>();
		lst.add(1L);
		int i=e;
		while (i<p.length){
			int L=lst.size();
			ArrayList<Long> pow=new ArrayList<Long>();
			long x=p[i];
			lp:while (true){
				pow.add(x);
				if (x<=MX/p[i])
					x*=p[i];
				else
					break lp;
			}
			for (int j=0;j<L;j++){
				long y=lst.get(j);
				lp:for (long xx:pow){
					if (y<=MX/xx)
						lst.add(y*xx);
					else
						break lp;
				}
			}
			i+=2;
		}
		return lst;
	}



	static long[] searchBS(long w,ArrayList<Long> ls1,ArrayList<Long> ls2,long k){
		long max=0;
		long cnt=0;

		for (long v:ls1){
			if (v>w)
				break;
			long y=w/v;
			int id=Collections.binarySearch(ls2,y);
			if (id<0)
				id=-id-2;
			if (id>=ls2.size())
				id=ls2.size()-1;
			if (id>=0){
				max=Math.max(max,v*ls2.get(id));
				cnt+=id+1;
				if (cnt>k)
					return new long[]{k+1,-1};

			} else {
				//log("==================problem==========");
				break;
			}
		}
		return new long[]{cnt,max};
	}

	static long[] search(long w,ArrayList<Long> ls1,ArrayList<Long> ls2,long k){
		long startTime=System.currentTimeMillis();
		long max=0;
		long cnt=0;
		int id1=0;
		;

		int lim1=ls1.size()-1;
		int lim2=ls2.size()-1;
		//int lim1=Collections.binarySearch(ls1,w);
		//int lim2=Collections.binarySearch(ls2,w);

		if (lim1<0)
			lim1=-lim1-2;

		if (lim2<0)
			lim2=-lim2-2;

		int id2=lim2;

		while (id1<=lim1){
			long v=ls1.get(id1);
			if (v>w)
				break;

			while (id2>=0 && w/ls2.get(id2)<v)
				id2--;

			/*
			if (id2==0){
				cnt+=lim1-id1+1;
				max=Math.max(ls1.get(lim1),max);
				break;
			}
			*/
			if (id2<0)
				break;
			max=Math.max(max,ls2.get(id2)*v);
			cnt+=id2+1;
			if (cnt>k)
				break;
			id1++;
		}
		//log(cnt+" "+max);
		//log(System.currentTimeMillis()-startTime);
		return new long[]{cnt,max};
	}

	static long[] search(long w,long[] ls1,long[] ls2,long k){
		long startTime=System.currentTimeMillis();
		long max=0;
		long cnt=0;
		int id1=0;
		;

		int lim1=ls1.length-1;
		int lim2=ls2.length-1;
	
		if (lim1<0)
			lim1=-lim1-2;

		if (lim2<0)
			lim2=-lim2-2;

		int id2=lim2;

		while (id1<=lim1){
			long v=ls1[id1];
			if (v>w)
				break;

			while (id2>=0 && w/ls2[id2]<v)
				id2--;

			if (id2<0)
				break;
			max=Math.max(max,ls2[id2]*v);
			cnt+=id2+1;
			if (cnt>k)
				break;
			id1++;
		}
		//log(cnt+" "+max);
		//log(System.currentTimeMillis()-startTime);
		return new long[]{cnt,max};
	}


	

	static void process() throws Exception {


		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader=new InputReader(System.in);

		//check();

		int n=reader.readInt();
		int[] p=new int[n];
		for (int i=0;i<n;i++){
			p[i]=reader.readInt();

		}
	
		k=reader.readLong();

		//ArrayList<Long> ls1=generate(p,0);
		//ArrayList<Long> ls2=generate(p,1);

		ArrayList<Long>[] bob=generate(p);
		ArrayList<Long> lls1=bob[0];
		ArrayList<Long> lls2=bob[1];

		long[] ls1=new long[lls1.size()];
		for (int i=0;i<lls1.size();i++)
			ls1[i]=lls1.get(i);

		long[] ls2=new long[lls2.size()];
		for (int i=0;i<lls2.size();i++)
			ls2[i]=lls2.get(i);

		
		log("step 1");
		Arrays.sort(ls1);
		Arrays.sort(ls2);
		
		//Collections.sort(ls1);
		//Collections.sort(ls2);

		log("step 2");
		long lo=1;
		long hi=MX;
		long ans=0;
		//log(ls1.size()+ls2.size()+" "+ls1.size()+" "+ls2.size());
		log("searching");
		int iter=0;
		long startTime=System.currentTimeMillis();
		loop:while (lo+1<hi){
			iter++;
			long mid=(lo+hi)/2;
			long cnt=0;

			long[] tmp=search(mid,ls1,ls2,k);
			cnt=tmp[0];
			max=tmp[1];
			//log("==============");


			//log("lo:"+lo+" hi:"+hi+" mid:"+mid+" max:"+max);
			//log("cnt:"+cnt+" k:"+k);
			if (cnt>k){
				hi=mid;
			}
			if (cnt<k){
				lo=mid;
			}
			if (cnt==k){
				lo=mid;
				break loop;
			}
		}
		long endTime=System.currentTimeMillis();
		log((endTime-startTime)+" ms");
		log("iter:"+iter);

		log("done");

		long[] tmp=search(lo,ls1,ls2,k);
		ans=tmp[1];//log(tmp);
		//ans=tmp[1];

		output(ans);

		try {
			out.close();
		}
		catch (Exception EX){}


	}


	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}




		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}


}