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$。否则，输出所需的最小总费用。

样例 #1

样例输入

3
100 99 9900
1 1 1

样例输出

2

样例 #2

样例输入

5
10 20 30 40 50
1 1 1 1 1

样例输出

-1

样例 #3

样例输入

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

样例输出

6

样例 #4

样例输入

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

样例输出

7237

说明/提示

在第一个样例测试中，单独购买一张卡牌是不够的：比如如果你只买了一张长度为 $100$ 的卡牌，则无法跳到编号不是 $100$ 的倍数的格子。最优做法是购买第一张和第二张卡牌，这样就可以跳到任意格子。

在第二个样例测试中，即使你买下了所有卡牌，也无法跳到编号不是 $10$ 的倍数的格子，因此应该输出 $-1$。

由 ChatGPT 5 翻译