#P1103D. Professional layer
-
ID: 4798
Type: RemoteJudge
3000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: 10
Uploaded By:
Hydro
Tags> Professional layer
Description
Cardbluff is popular sport game in Telegram. Each Cardbluff player has ever dreamed about entrance in the professional layer. There are judges now in the layer and you are trying to pass the entrance exam. You have a number — your skill in Cardbluff.
Each judge has a number — an indicator of uncertainty about your entrance to the professional layer and a number — an experience playing Cardbluff. To pass the exam you need to convince all judges by playing with them. You can play only one game with each judge. As a result of a particular game, you can divide the uncertainty of -th judge by any natural divisor of which is at most . If GCD of all indicators is equal to , you will enter to the professional layer and become a judge.
Also, you want to minimize the total amount of spent time. So, if you play with judges with total experience you will spend seconds.
Print minimal time to enter to the professional layer or if it's impossible.
There are two numbers in the first line and (, ) — the number of judges and your skill in Cardbluff.
The second line contains integers, where -th number () — the uncertainty of -th judge
The third line contains integers in the same format (), — the experience of -th judge.
Print the single integer — minimal number of seconds to pass exam, or if it's impossible
Input
There are two numbers in the first line and (, ) — the number of judges and your skill in Cardbluff.
The second line contains integers, where -th number () — the uncertainty of -th judge
The third line contains integers in the same format (), — the experience of -th judge.
Output
Print the single integer — minimal number of seconds to pass exam, or if it's impossible