Jumping Minho

There is an infinitely long one-dimensional coordinate line whose points are the negative integers, $0$, and the positive integers. Minho stands on one point of this line.

In front of Minho there is a shop that sells $n$ cards. Card $i$ is labeled with a length $l_i$ and a price $c_i$. If Minho pays $c_i$ won for that card, he can jump from any point $x$ to $x - l_i$ or to $x + l_i$.

At the start Minho owns no card, so he cannot leave the point he stands on. Once he spends money on cards, he can jump to other points.

Minho wants to buy some cards so that every point of the line becomes reachable. If such a purchase exists, he wants to spend as little money as possible.

Write a program that decides whether some set of cards makes every point reachable and, when it does, computes the smallest possible cost.

The first line contains the number of cards $n$ ($1 \le n \le 300$).

The second line contains the lengths of the $n$ cards, $l_1, l_2, \ldots, l_n$ ($1 \le l_i \le 10^9$).

The third line contains the prices of the $n$ cards, $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^5$).

If no set of cards makes every point reachable, print $-1$.

Otherwise, print the smallest cost among the purchases that make every point reachable.