12859번 - 점프하는 민호

문제

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

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

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

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

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

입력

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

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

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

출력

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

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

제한

힌트