블록 분리하기

소들은 사실 퍼즐을 아주 좋아합니다! 세 개의 단단한 물체로 이루어진 기계식 퍼즐이 있습니다. 각 물체는 $1 \times 1$ 단위 정사각형들을 서로 붙여 만든 것으로, 상하좌우(북·남·동·서)로 인접한 정사각형을 따라 어느 칸에서든 물체의 다른 어떤 칸으로도 이동할 수 있다는 의미에서 '연결된' 모양입니다.

물체는 북·남·동·서 중 한 방향으로 한 칸씩 반복해서 밀어 움직일 수 있습니다. 퍼즐의 목표는 세 물체를 서로 '분리'하는 것입니다. 즉, 각 물체를 감싸는 최소 직사각형(바운딩 박스)이 서로 양(+)의 넓이로 겹치지 않도록 만드는 것입니다. 세 물체의 모양과 위치가 주어질 때, 물체들을 분리하는 데 필요한 최소 이동 횟수(한 칸 밀기 1번을 1로 셈)를 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N_1$, $N_2$, $N_3$. 각각 물체 1, 2, 3을 이루는 단위 정사각형의 개수입니다.
• 다음 $N_1$개의 줄: 물체 1을 이루는 각 정사각형의 남서쪽(왼쪽 아래) 꼭짓점 좌표 $(x, y)$.
• 다음 $N_2$개의 줄: 물체 2를 이루는 각 정사각형의 남서쪽 꼭짓점 좌표.
• 다음 $N_3$개의 줄: 물체 3을 이루는 각 정사각형의 남서쪽 꼭짓점 좌표.

모든 좌표는 $0$ 이상 $9$ 이하입니다.

• 첫째 줄: 세 물체를 분리하기 위해 필요한 최소 이동 횟수. 어떤 방법으로도 분리할 수 없으면 $-1$을 출력합니다.

예를 들어 물체 1이 $12$개, 물체 2가 $3$개, 물체 3이 $5$개의 정사각형으로 이루어진 경우를 생각해 봅시다. 물체 3을 동쪽으로 한 칸, 물체 2를 북쪽으로 한 칸, 물체 1을 서쪽으로 세 칸 밀면 세 물체의 바운딩 박스가 더 이상 겹치지 않게 되어, 총 $5$번의 이동으로 분리할 수 있습니다.