Super Ugly Number

medium

Unknown

Question Solve Solutions

1. You are given an array(arr) of size k which contains prime numbers in ascending order, and an integer N.
2. You have to find Nth super ugly number.
3. Super ugly number is defined as the number whose prime factors are elements of the given array.

Assumption -&gt; 1 is the first super ugly number.

Input Format

A number K arr1 arr2.. K prime numbers in ascending order A number N

Output Format

A number representing Nth super ugly number.

Constraints

1 &lt;= K &lt;= 100
1 &lt;= arr[i] &lt;= 1000
1 &lt;= N &lt;= 10^6

Example

Input

4
3 5 7 11
13

Output

Find Transition Point

Related Questions

easy Is Prime easy Prime Till N easy Reverse Integer easy GCD easy Fibonacci easy Fib Till N easy Exit Point of a matrix easy Placing N Queen in a matrix easy Arranging Vowels And Consonants easy Addition Of Two Linked List easy Circular Linked List easy Sort The Absolute List easy Decimal Number From Binary Linked List easy Find the largest rectangle in a matrix easy Count Pairs Having Sum X easy Delete alternate nodes of linked list