← 목록으로

빨간, 파란 점 연결

평면에 R개의 빨간 점들과 B개의 파란 점들이 있다. 그리고 이 중 어떠한 세 점도 한 직선 위에 있지 않으며, 세 점으로 만들어지는 삼각형 내부에 다른 점이 존재하지도 않는다.

우리는 점들을 정점으로 생각하고 두 점을 연결하는 선분을 간선으로 생각해서 트리를 그릴 것이다. 여기서 트리란 임의의 두 정점 사이에 항상 경로가 존재하고 그 경로는 단 하나인 그래프이다.

우리가 그리는 트리는 주어진 모든 점을 정점으로 가져야 하고, 모든 간선은 빨간 점과 파란 점을 연결하며 임의의 서로 다른 두 간선이 주어진 점이 아닌 부분에서 서로 교차하지 않아야 한다.

이런 식으로 그린 트리에서 점 (x, y)와 (u, v)를 연결하는 간선의 가중치는 |x - u| + |y - v| 로 계산된다.

R+B개의 점이 주어지고 위 조건을 만족하는 트리를 그릴 때, 모든 간선의 가중치의 합을 최소화하여 그 최솟값을 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에 빨간 점의 개수를 나타내는 정수 R과 파란 점의 개수를 나타내는 정수 B가 공백으로 구분되어 주어진다. (0 ≤ R, B ≤ 200; 2 ≤ R+B)

그다음 R개의 줄 각각에 빨간 점 하나의 좌표 (x, y)를 나타내는 두 정수 x, y가 주어진다. (-107 ≤ x, y ≤ 107)

그다음 B개의 줄 각각에 파란 점 하나의 좌표 (x, y)를 나타내는 두 정수 x, y가 주어진다. (-107 ≤ x, y ≤ 107)

단, 어떠한 세 점도 한 직선 위에 있지 않으며, 세 점으로 만들어지는 삼각형 내부에 다른 점이 존재하지도 않는다.

출력 형식

첫 줄에 문제의 조건을 만족하는 트리를 그릴 때, 모든 간선의 가중치의 합의 최솟값을 출력한다. 만약, 문제의 조건을 만족하는 트리가 존재하지 않으면 -1을 출력한다.

입력 예제 1

2 2
-2 2
2 2
-2 -2
2 -2

출력 예제 1

16

입력 예제 2

4 0
-2 2
2 2
-2 -2
2 -2

출력 예제 2

-1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설