Một mảnh giấy kích thước \(n× n\) ô (với \(n\) là số chẵn), được chia theo dạng domino. Cụ thể, trên mảnh giấy chia ra làm \((n× n)/2\) hình domino. Các hình được đánh số hiệu từ 1 đến \((n× n)/2\) và có kích thước \(1× 2\) ô hoặc \(2× 1\) ô, mỗi ô ghi số hiệu của thanh đó.

Cần cắt một hình chữ lớn nhất thỏa mãn các điều kiện sau:

• Các cạnh của hình chữ nhật song song với các cạnh của mảnh giấy;
• Hình chữ nhật nằm hẳn bên trong mảnh giấy;
• Hình chữ nhật chứa nguyên vẹn các hình domino.

Ví dụ, mảnh giấy kích thước 6×6.

Yêu cầu: Cho thông tin mảnh giấy, tìm diện tích hình chữ nhật lớn nhất thỏa mãn yêu cầu.

Input

• Dòng đầu chứa số nguyên dương \(n\);
• Tiếp theo là \(n\) dòng, mỗi dòng chứa \(n\) số mô tả mảnh giấy. Các số có giá trị từ 1 đến \((n× n)/2\) và mỗi số xuất hiện đúng hai lần.

Output

• Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật lớn nhất tìm được.

Constraints

• \(n\leq 1000\)

Scoring

• Subtask \(1\) (\(45\%\) số điểm): \(n\leq 100\)
• Subtask \(2\) (\(20\%\) số điểm): \(n\leq 500\)
• Subtask \(3\) (\(35\%\) số điểm): Không có ràng buộc gì thêm

Example

6
1 1 4 4 13 14
2 3 3 5 13 14
2 6 7 5 12 12
9 6 7 10 10 15
9 8 8 11 11 15
16 16 17 17 18 18 

8