猫猫跳
题号:NC232854
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一只猫猫想要从位置0开始在一条有无限多格(编号可能是任意整数)的道路上随意游走,但慢慢走实在是太慢了。这时,猫猫收到了霍格沃茨的雪鸮送来的n张魔法卡,每张魔法卡需要花费c_i的时间学习,学习之后可以快速移动l_i的距离,即从x(x-l_i)。猫猫准备学习若干个魔法,并依靠所学的魔法快速走遍这条道路。

猫猫想要尽快学会魔法实现自己的愿望,你可以帮猫猫求出最短的学习时间吗?

输入描述:

第一行输入一个整数n (),表示魔法卡的数量。
第二行输入n个整数l_i (),表示每张魔法卡的移动距离。
第三行输入n个整数c_i (),表示学习每张魔法卡所需要的时间。

输出描述:

如果可以通过学习若干个魔法实现快速走遍道路,则输出猫猫学习魔法的最短时间花费,否则输出-1
示例1

输入

复制
3
100 99 9900
1 1 1

输出

复制
2

说明

选择100和99两个魔法卡即为需要时间最短的方案。
示例2

输入

复制
5
10 20 30 40 50
1 1 1 1 1

输出

复制
-1

说明

编号不是10的倍数的格子无论如何也无法到达,所以输出-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