D. Лиса и прыжки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Лиса Ciel играет в игру. Она стоит на бесконечной длинной ленте с ячейками, пронумерованными целыми числами (положительными, отрицательными и нулем). В начале она стоит в ячейке 0.

Также есть n карточек, каждая из которой характеризуется числом li и стоимостью ci. Если лиса заплатит ci долларов, то она сможет применить i-ю карточку. После применения i-й карточки лиса сможет совершать прыжки длины li, то есть, от ячейки x к ячейке (x - li) или ячейке (x + li).

Лиса хочет научиться прыгать в любую ячейку на ленте (возможно, посетив некоторые промежуточные ячейки). Для достижения этой цели она хочет купить некоторое количество карточек, заплатив при этом как можно меньше денег.

Если этого возможно добиться, посчитайте минимальную стоимость.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 300), количество карточек.

Во второй строке записано n чисел li (1 ≤ li ≤ 109), длины прыжков, указанные на карточках.

В третьей строке записано n чисел ci (1 ≤ ci ≤ 105), стоимости карточек.

Выходные данные

Если невозможно купить некоторое количество карточек и получить возможность прыгнуть в любую ячейку, выведите -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
Примечание

В первом примере недостаточно купить одну карточку: например, если купить карточку для прыжков длины 100, то нельзя прыгнуть ни в одну ячейку, номер которой не кратен 100. Оптимальный способ — купить первую и вторую карточку, тогда можно будет добраться до любой ячейки.

Во втором примере, даже если купить все карточки, то вы не сможете прыгнуть ни в одну ячейку, номер которой не кратен 10, так что ответ — -1.