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。