← 返回题目列表

Codeforces · 510/D

D. 狐狸和跳跃

中文机器翻译题面 查看原题

Fox Ciel 正在玩游戏。在这个游戏中,有一个无限长的磁带,其中的单元格由整数(正数、负数和零)索引。一开始她站在0号牢房。

同样有n张卡,每张卡有2个属性:长度li和成本ci。如果她支付 ci 美元,那么她可以申请第 i 张卡。在应用第 i 张卡片后,她能够进行长度为 li、i 的跳跃。 e.从单元格 x 到单元格 (x - li) 或单元格 (x + li)。

她希望能够跳转到磁带上的任何单元格(可能访问一些中间单元格)。为了实现这个目标,她想买一些卡,花尽可能少的钱。

如果可能,请计算最小成本。

输入

第一行包含一个整数n (1 ≤ n ≤ 300),卡片数量。

第二行包含n个数字li (1 ≤ li ≤ 109),即卡片的跳跃长度。

第三行包含n个数字ci (1 ≤ ci ≤ 105),即卡片的费用。

输出

如果无法购买一些卡并变得能够跳转到任何单元格,则输出-1。否则输出购买此类卡牌的最低成本。

示例

输入 #1

3
100 99 9900
1 1 1

输出 #1

2

输入 #2

5
10 20 30 40 50
1 1 1 1 1

输出 #2

-1

输入 #3

7
15015 10010 6006 4290 2730 2310 1
1 1 1 1 1 1 10

输出 #3

6

输入#4

8
4264 4921 6321 6984 2316 8432 6120 1026
4264 4921 6321 6984 2316 8432 6120 1026

输出#4

7237

注意

在第一个样本测试中,购买一张卡是不够的:例如,如果您购买长度为100的卡,则无法跳转到索引不是100倍数的任何单元格。最好的方法是购买第一张和第二张卡,这样您就可以跳转到任何单元格。

在第二个样本测试中,即使购买了所有卡,也无法跳转到索引不是 10 倍数的任何单元格,因此应该输出 -1。