597. Super Ugly Number

0

Medium

A super ugly number is a positive integer that has prime factors from the array primes.
Given an integer n and an array of integers primes, find and print the nth super ugly number.
The nth super ugly number will be within the range of a 32-bit signed integer.

Input Format

The first line contains the value of n.
The second line contains the size of the primes array.
The third line contains the elements of the primes array.

Output Format

An integer representing the nth super ugly number.

Example

Input

12
4
2 7 13 19

Output

32

Constraints

1 <= n <= 10^5
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is a prime number.
All values of primes are unique and sorted in ascending order.

Loading...

View Submissions

Console