题目描述

狐仙小月正在玩一个神奇的跳跃游戏。在这个游戏中，有一条无限长的神秘轨道，轨道上的每一个格子都用整数编号（可以是正数、负数，也可以是零）。游戏一开始，小月站在编号为 0 的格子上。

游戏中提供了 $n$ 张跳跃卡，每张跳跃卡都有两个属性：跳跃距离 $l_i$ 和花费 $c_i$。当小月支付 $c_i$ 金币后，她就可以使用第 $i$ 张跳跃卡，从当前格子跳到距离 $l_i$ 的任意位置（可以向左跳，也可以向右跳）。

小月的目标是能够跳到轨道上的任意格子（可能需要经过一些中间格子）。为了实现这个目标，她需要挑选一些跳跃卡，并支付尽可能少的金币。

如果她能实现目标，请计算最少需要支付多少金币；如果目标无法实现，请输出 $-1$。

输入格式

第一行：一个整数 $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$。

样例

3
100 99 9900
1 1 1

2

5
10 20 30 40 50
1 1 1 1 1

-1

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

6

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

7237

解释

对于第一个样例，购买第 1 张卡（$l_1 = 100, c_1 = 1$）和第 2 张卡（$l_2 = 99, c_2 = 1$），小月就可以跳到任意格子，所需金币为 $1 + 1 = 2$。

对于第二个样例，无论购买哪几张跳跃卡，小月都无法跳到所有编号不为 $10$ 的倍数的格子，无法实现目标。