题目描述

小明在上电脑课的时候，写了一个游戏。

游戏的内容是：在 $n \times n$ 的矩阵里，有若干个敌人。你可以选择一个没有敌人的位置放置激光炮，激光炮会朝左上角和左下角两个方向发射激光，能消灭与激光炮距离为 $1$ 的敌人。

目前只能部署一次激光炮，请问把激光炮放置在哪个位置上消灭的敌人数量最多。

输入格式

第一行一个正整数 $n$ ，表示矩阵的大小。

接下来 $n$ 行，每行 $n$ 个整数 $x$ ($0 \le x \le 9$)，表示敌人的数量。

输出格式

一个整数，表示最多能消灭的敌人数量。

样例数据

4
1 1 1 0
2 1 0 1
0 0 1 0
1 3 1 1

3

提示/说明

对于100%的数据，$1 \le n \le 1000$