All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Assorted Arrangement
Tag(s):

Algorithms, Easy, Greedy

Problem
Editorial
Analytics

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

SAMPLE INPUT
6 4
3 6 7 9
1 2 1 1 4 3
SAMPLE OUTPUT
42
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications