CF510D Fox And Jumping

Fox Ciel 正在玩一个游戏。游戏中有一条无限长的带子，带子的每个格子都有一个整数编号（可以是正数、负数或零）。一开始，她站在 $0$ 号格子上。 现在有 $n$ 张卡牌，每张卡牌有两个属性：长度 $l_i$ 和费用 $c_i$。如果她支付 $c_i$ 美元，她就可以获得第 $i$ 张卡牌。在获得第 $i$ 张卡牌后，她就能够每次跳跃 $l_i$ 的距离，即从格子 $x$ 跳到格子 $x-l_i$ 或格子 $x+l_i$。 她希望能够跳到带子的任意一个格子（可以经过一些中间格子）。为了实现这个目标，她想要花尽量少的钱买一些卡牌。 如果可以实现这个目标，请计算出所需的最小总费用。

第一行包含一个整数 $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$），表示每张卡牌的费用。

如果无论如何都无法通过购买若干卡牌达到跳到任意格子的目的，输出 $-1$。否则，输出所需的最小总费用。

在第一个样例测试中，单独购买一张卡牌是不够的：比如如果你只买了一张长度为 $100$ 的卡牌，则无法跳到编号不是 $100$ 的倍数的格子。最优做法是购买第一张和第二张卡牌，这样就可以跳到任意格子。 在第二个样例测试中，即使你买下了所有卡牌，也无法跳到编号不是 $10$ 的倍数的格子，因此应该输出 $-1$。 由 ChatGPT 5 翻译