Một trong những cánh đồng của Farmer John đặc biệt gồ ghề, và ông muốn mua một chiếc máy kéo mới để lái trên đó. Cánh đồng được mô tả bởi một lưới \(N \times N\) gồm các độ cao nguyên không âm (\(1 \le N \le 500\)). Một chiếc máy kéo có khả năng di chuyển từ một ô sang ô kề cạnh (một bước về phía bắc, đông, nam hoặc tây) có độ chênh cao \(D\) có giá chính xác \(D\) đơn vị tiền.

FJ muốn trả đủ tiền cho chiếc máy kéo để khi bắt đầu từ một ô nào đó trên cánh đồng, ông có thể lái máy kéo đi thăm ít nhất một nửa số ô của cánh đồng (nếu tổng số ô là số lẻ, ông muốn thăm ít nhất một nửa số ô được làm tròn lên). Hãy giúp ông tính chi phí tối thiểu cần thiết để mua một chiếc máy kéo có thể thực hiện nhiệm vụ này.

Dữ liệu vào

• Dòng đầu tiên chứa giá trị \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên không âm cách nhau bởi dấu cách (mỗi số không vượt quá \(1\) triệu), mô tả một hàng của cánh đồng FJ.

Dữ liệu ra

In ra chi phí tối thiểu của một chiếc máy kéo có khả năng di chuyển trên ít nhất một nửa cánh đồng của FJ.

Ví dụ

5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3

3

Nguồn

USACO 2013 February Contest, Silver — Problem 2: Tractor

Tác giả đề: Kalki Seksaria và Brian Dean, 2013.