U628784 Laz玩游戏

Laz正在玩一个游戏。游戏中有一条无限长的纸带，单元格由整数（正数、负数和零）索引。开始时她站在单元格0处。另外还有n张卡片，每张卡片有两个属性：长度li和成本ci。如果她支付ci美元，就可以使用第i张卡片。使用第i张卡片后，她就能进行长度为li的跳跃，即从单元格x跳到单元格(x - li)或单元格(x + li)。她希望能够跳到纸带上的任意单元格（可能需要经过一些中间单元格）。为了实现这个目标，她想要购买一些卡片，并尽可能少花钱。如果可能的话，请计算最小成本。

第一行包含一个整数 n (1 ≤ n ≤ 1000)，表示卡牌的数量。 第二行包含 n 个数字 li (1 ≤ li ≤ 10^9)，表示每张卡牌的跳跃长度。 第三行包含 n 个数字 ci (1 ≤ ci ≤ 10^5)，表示每张卡牌的成本。

如果无法通过购买卡片实现跳跃到任意单元格，则输出-1。否则输出满足条件的卡片组合的最低购买成本。

在第一个样例测试中，仅购买一张卡是不够的：例如，若你购买长度为100的卡片，则无法跳转到非100倍数的任意单元格。最佳方案是同时购买第一张和第二张卡片，这样便能抵达所有单元格。