Giải bài trực tuyến

Cho N hình chữ nhật trên mặt phẳng Oxy. Các hình chữ nhật này có toạ độ nguyên và có các cạnh song song với trục toạ độ. Ở mỗi lượt, các hình chữ nhật có thể đứng yên hoặc di chuyển theo 8 hướng:

• sang trái 1 đơn vị
• sang phải 1 đơn vị
• lên trên 1 đơn vị
• xuống dưới 1 đơn vị
• sang trái và lên trên 1 đơn vị
• sang trái và xuống dưới 1 đơn vị
• sang phải và lên trên 1 đơn vị
• sang phải và xuống dưới 1 đơn vị

Hãy xác định sau ít nhất bao nhiên lượt thì N hình chữ nhật ban đầu sẽ được di chuyển đến các vị trí mới sao cho phần diện tích giao nhau của tất cả N hình chữ nhật này lớn hơn hoặc bằng 1.

Dữ liệu vào

Dòng đầu tiên ghi số N là số lượng các hình chữ nhật.

Tiếp theo là N dòng, mỗi dòng ghi 4 số nguyên x₁, y₁, x₂, y₂ thể hiện hình chữ nhật có góc trái dưới là (x₁, y₁) góc phải trên là (x₂, y₂).

Dữ liệu ra

In ra số lượt di chuyển tối thiểu.

Giới hạn

Subtask 1 (30% số điểm)

• 2 ≤ N ≤ 200
• |tọa độ| ≤ 100
• Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 2 (40% số điểm)

• 200 < N ≤ 10⁵
• |toạ độ| ≤ 2 * 10⁹
• Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 3 (30% số điểm)

• 200 < N ≤ 10⁵
• |tọa độ| ≤ 2 * 10⁹

Ví dụ

Input:
3
0 0 1 1
0 0 2 3
2 3 4 5

Output:
2

Giải thích

Sau 2 lượt:

• Hình 1: Di chuyển lên trên 1 đơn vị rồi sau đó di chuyển chéo lên phải 1 đơn vị.
• Hình 2: Đứng yên.
• Hình 3: Di chuyển chéo xuống trái 1 đơn vị.