Bạn phát hiện một khu khoáng sản trên sao Hỏa và muốn tiến hành khai thác. Tuy nhiên do điều kiện hạn chế bạn chỉ có thể sử dụng một robot tự hành tiến hành thu thập tài nguyên ở đó. Robot mô phỏng khu vực khoáng sản trên là một lưới ô vuông kích thước \(N \cdot N\). Robot xuất phát tại ô \((1,1)\) và kết thúc tại ô \((N,N)\). Robot chỉ được di chuyển sang phải hoặc xuống dưới. Mỗi ô \((i,j)\) có phần khoáng sản trị giá \(A[i][j]\).

Robot có hai trạng thái thu hoạch: ON và OFF. Do từ trường trên sao Hỏa đặc biệt nên khi robot bước vào ô khoáng sản có giá trị lẻ, nó sẽ đảo trạng thái ON thành OFF và ngược lại.

Quy tắc khai thác như sau:

• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị lẻ: nó sẽ thu hoạch khoáng sản tại vị trí đó và thay đổi trạng thái thành OFF.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị lẻ: nó chỉ thay đổi trạng thái thành ON và không khai thác khoáng sản tại ô đó.
• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị chẵn: nó sẽ thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái ON.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị chẵn: nó sẽ không thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái OFF.

Yêu cầu: Tính tổng giá trị phần quà tối đa có thể lấy được. Biết rằng ban đầu robot có trạng thái thu hoạch là ON.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \le 500\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên dương \(A[i][j]\) (\(A[i][j] \le 10^6\)).

Output

• Ghi ra một số nguyên duy nhất là tổng giá trị phần quà lớn nhất có thể.

Example

3
1 2 3
4 5 6
7 8 9

18

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 15\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 100\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 500\).