빨간, 파란 점 연결

NYPC 2019 · 예선

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

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

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

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

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

입력 형식

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

그다음 RR개의 줄 각각에 빨간 점 하나의 좌표 (x,y)(x, y)를 나타내는 두 정수 xx, yy가 주어진다. (107x,y107-10^7 \le x, y \le 10^7)

그다음 BB개의 줄 각각에 파란 점 하나의 좌표 (x,y)(x, y)를 나타내는 두 정수 xx, yy가 주어진다. (107x,y107-10^7 \le x, y \le 10^7)

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

출력 형식

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

예제 1

입력

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

출력

16

예제 2

입력

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

출력

-1

채점 방식

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

종류 1: 32

R,B40R, B \le 40

종류 2: 68

별다른 제약조건 없음.

해설