CF510D.Fox And Jumping

Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell 0.

There are also n cards, each card has 2 attributes: length l__i and cost c__i. If she pays c__i dollars then she can apply i-th card. After applying i-th card she becomes able to make jumps of length l__i, i. e. from cell x to cell (x - l__i) or cell (x + l__i).

She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible.

If this is possible, calculate the minimal cost.

小狐狸 Ciel 正在玩一个游戏。游戏中有一条无限长的纸带，纸带上的格子用整数（正数、负数和零）编号。游戏开始时，她位于编号为 0 的格子上。

此外还有 $n$ 张卡片，每张卡片有两个属性：长度 $l_i$ 和费用 $c_i$。若她支付 $c_i$ 美元，则可以使用第 $i$ 张卡片。使用第 $i$ 张卡片后，她便能进行长度为 $l_i$ 的跳跃，即可以从格子 $x$ 跳到格子 $(x - l_i)$ 或格子 $(x + l_i)$。

她希望能够在纸带上跳到任意一个格子（途中可能经过一些中间格子）。为达成这一目标，她打算购买若干张卡片，并希望所付总金额尽可能少。

如果该目标可以实现，请计算所需的最小费用。

The first line contains an integer n (1 ≤ n ≤ 300), number of cards.

The second line contains n numbers l__i (1 ≤ l__i ≤ 109), the jump lengths of cards.

The third line contains n numbers c__i (1 ≤ c__i ≤ 105), the costs of cards.

第一行包含一个整数 $n$（$1 \leq n \leq 300$），表示卡片的数量。

第二行包含 $n$ 个整数 $l_i$（$1 \leq l_i \leq 10^9$），表示各卡片的跳跃长度。

第三行包含 $n$ 个整数 $c_i$（$1 \leq c_i \leq 10^5$），表示各卡片的花费。

If it is impossible to buy some cards and become able to jump to any cell, output -1. Otherwise output the minimal cost of buying such set of cards.

如果无法通过购买若干张卡片使得能够跳到任意一个格子，则输出 -1；否则，输出购买这样一组卡片的最小花费。

In first sample test, buying one card is not enough: for example, if you buy a card with length 100, you can't jump to any cell whose index is not a multiple of 100. The best way is to buy first and second card, that will make you be able to jump to any cell.

In the second sample test, even if you buy all cards, you can't jump to any cell whose index is not a multiple of 10, so you should output -1.

在第一个样例测试中，仅购买一张卡片是不够的：例如，如果你购买一张长度为 100 的卡片，则你无法跳转到任意索引不是 100 的倍数的格子。最优方案是购买第一张和第二张卡片，这样你便能够跳转到任意格子。

在第二个样例测试中，即使你购买了所有卡片，你也无法跳转到任意索引不是 10 的倍数的格子，因此你应该输出 -1。