Một sự thật ít người biết về loài bò là chúng rất thích giải đố! Nhân dịp sinh nhật Bessie, Farmer John tặng cô một câu đố cơ khí thú vị để giải. Câu đố gồm ba vật thể rắn, mỗi vật thể được tạo thành từ các ô vuông đơn vị \(1 \times 1\) dán với nhau. Mỗi vật thể là một hình "liên thông", theo nghĩa là ta có thể đi từ một ô vuông bất kỳ của vật thể đến bất kỳ ô vuông nào khác trên cùng vật thể bằng cách bước qua các ô thuộc vật thể theo hướng bắc, nam, đông hoặc tây.

Một vật thể có thể được di chuyển bằng cách trượt nó lặp đi lặp lại một đơn vị về phía bắc, nam, đông hoặc tây. Mục tiêu của câu đố là di chuyển các vật thể sao cho chúng tách rời nhau, tức là các hình chữ nhật bao của chúng không còn có bất kỳ phần giao nào với diện tích dương. Với hình dạng và vị trí của ba vật thể, nhiệm vụ của bạn là giúp Bessie xác định số lần trượt riêng lẻ tối thiểu cần thiết để tách các vật thể ra.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N1\), \(N2\) và \(N3\), cách nhau bởi dấu cách, lần lượt mô tả số ô vuông đơn vị tạo nên vật thể 1, 2 và 3.
• Các dòng từ 2 đến \(1+N1\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 1. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1\) đến \(1+N1+N2\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 2. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1+N2\) đến \(1+N1+N2+N3\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 3. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.

Dữ liệu ra

• Dòng 1 chứa số lần di chuyển tối thiểu cần thiết để tách ba vật thể, hoặc -1 nếu không thể tách chúng ra.

Ví dụ

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

5

Nguồn

USACO 2012 US Open, Silver Division — Unlocking Blocks (Silver)

Tác giả: Brian Dean, 2012.