All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Assorted Arrangement

Algorithms, Greedy Algorithms


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.


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

6 4
3 6 7 9
1 2 1 1 4 3

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}.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications