题目描述

给出 $n$ 张卡片，分别有 $l_i$ 和 $c_i$。在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 -1。

输入格式

第一行一个整数 $n$（$1 \le n \le 300$）。

第二行 $n$ 个整数 $l_i$（$1 \le l_i \le 10^9$）。

第三行 $n$ 个整数 $c_i$（$1 \le l_i \le 10^5$）。

输出格式

一行一个整数表示答案。

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