You have a set of n distinct positive numbers. You also have m colors. Your colors are labeled from 1 to m. You're also given a list c with m distinct integers.
You paint the numbers according to the following rules: For each i in order from 1 to m, paint numbers divisible by c[i] with color i. If multiple rules apply to a number, only the last rule applies.
You sorted your set of numbers and painted them. It turns out that no number was left unpainted. Unfortunately, you lost the set of numbers you had originally. Return the smallest possible value of the maximum number in your set. The input will be constructed such that it's guaranteed there is at least one set of numbers that is consistent with the given information.
Input format
The first line will contain two space separated integers n,m.
The second line will contain m space separated integers. The i-th integer in this line denotes c[i].
The third line will contain n space separated integers. This j-th integer in this line denotes the color of the j-th smallest number in your set.
Output format
Print a single integer on its own line, the minimum possible value of the largest number in your set.
Constraints
For all subtasks:
1 ≤ n
1 ≤ m
Elements in c will be in strictly increasing order.
1 ≤ c[i] ≤ 100
Subtask 1 (65 pts):
n ≤ 100
m = 2
c[2] is divisible by c[1]
Subtask 2 (25 pts):
n ≤ 100,000
m ≤ 5
Subtask 3 (10 pts):
n ≤ 100,000
m ≤ 50
For the first sample, we have four colors and six numbers in our set. All numbers with color 1 are divisible by 3, but not 6, 7, or 9. All numbers with color 2 are divisible by 6, but not 7 or 9. All numbers with color 3 are divisible by 7 but not 9. All numbers with color 4 are divisible by 9. One example of the original set could have been {3,6,15,33,36,42}.
