시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 92 | 52 | 38 | 55.072% |
음의정수, 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을 출력한다.
가능한 경우가 존재한다면 사용해야 하는 비용들 중 가장 적은 비용을 출력한다.
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