시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 30 23 14 70.000%

문제

음의정수, 0, 양의정수로 표현할 수 있는 무한히 긴 1차원 좌표가 있다. 이런 1차원 좌표위의 한 점에 민호가 서있다.

그리고 민호의 앞에는 n개의 카드들을 파는 상점이 있다. 각각의 카드 li와 ci라는 두개의 값을 가지고 있다. 만약 민호가 ci원을 사용해 카드를 산다면 임의의 점 x에서 (x - li)또는 (x + li)로 점프를 할 수가 있게 된다.

처음 민호는 아무런 카드를 가지고 있지 않기 때문에 처음 서있던 위치에서 움직일 수가 없다. 하지만 돈을 써서 카드를 사면 점프를 해 다른 점들로 이동을 할 수 있게 된다.

민호는 몇개의 카드를 사서 무한히 긴 1차원 좌표에서 갈수 없는 점이 존재하지 않았으면 한다. 만약 모든 점들을 갈 수 있는 경우가 존재한다면 가능한 적은 비용을 사용해 카드를 사고 싶다.

몇개의 카드를 사서 모든 점들을 방문 할 수 있는지 알아보고 가능한 경우 중 가장 적은 비용을 계산하는 프로그램을 작성하자.

입력

첫 번째 줄에는 카드의 개수 n (1 ≤ n ≤ 300) 이 주어진다.

두 번째 줄에는 n개의 카드가 가지고 있는 li (1 ≤ li ≤ 109)이 주어진다.

세 번째 줄에는 n개의 카드가 가지고 있는 ci (1 ≤ ci ≤ 105)이 주어진다.

출력

만약 몇개의 카드를 사서 모든 점들을 갈 수 있는 경우가 존재하지 않다면 -1을 출력한다.

가능한 경우가 존재한다면 사용해야 하는 비용들 중 가장 적은 비용을 출력한다.

예제 입력 1

3
100 99 9900
1 1 1

예제 출력 1

2

예제 입력 2

5
10 20 30 40 50
1 1 1 1 1

예제 출력 2

-1

예제 입력 3

7
15015 10010 6006 4290 2730 2310 1
1 1 1 1 1 1 10

예제 출력 3

6

예제 입력 4

8
4264 4921 6321 6984 2316 8432 6120 1026
4264 4921 6321 6984 2316 8432 6120 1026

예제 출력 4

7237