大魔法师牛可乐

题号：NC235543
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

水平方向上有无限个魔法阵，每个整数坐标上都有一个魔法阵，大魔法师牛可乐初始位于坐标为 $0$ 的魔法阵。

魔法商店正在出售 $n$ 种魔法，第 $i$ 种魔法的价格是 $c_i$ ，购买了某种魔法后，牛可乐可以无限次使用该魔法。假设牛可乐当前位于坐标为 $x$ 的魔法阵，第 $i$ 种魔法可以将牛可乐传送到坐标为 $x-l_i$ 或 $x+l_i$ 的魔法阵。

牛可乐想知道他是否可以通过购买一些魔法使他能够到达任意一个魔法阵。

如果可以，请计算出实现这一目的的最小花费。

输入描述:

第一行一个整数 ，代表魔法的种类数。

第二行包含  个整数 ，代表第  种魔法的传送距离。

第三行包含  个整数 ，代表第  种魔法的价格。

输出描述:

如果可以，输出一行一个整数，表示最小花费。否则输出 。

示例1

输入

复制

3
2 3 4
2 3 4

输出

复制

说明

如果只选择一种魔法，牛可乐无法实现目标，如果选择第二种和第三种魔法或者第一种和第二种魔法，牛可乐可以到达任意魔法阵，其中最小花费的选择第一种和第二种，花费为 。

示例2

输入

复制

5
10 20 30 40 50
1 1 1 1 1

输出

复制

-1