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

Cho bức tường NxN được xây bởi N² / 2 viên gạch kích thước 2x1. Trên mỗi viên gạch ghi 2 số nguyên từ 1 đến N² / 2.

Ví dụ hình vẽ như sau :

Bạn hãy phá bức tường trên để tạo thành 1 cửa sổ hình chữ nhật thỏa mãn :

- Các cạnh cửa sổ song song với cạnh bức tường

- Cửa sổ không chạm vào cạnh của bức tường

- Phải phá cả viên gạch, không được phá nửa viên gạch

- Tổng diện tích phá là lớn nhất.

Input

- Dòng 1 : N (N ≤ 1000)

- Dòng 2 : N dòng tiếp theo gồm N số.

Output

- 1 số duy nhất là diện tích lớn nhất bị phá.

Example

Input:

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 

Output:
8