最大总效益

题目描述

某区域被划分为 n x n 的网格区域，用于部署 5G 网络。初始时，所有网格都处于信号未强化覆盖状态。

网络工程师可以执行任意次优化操作：选择任意一列，对该列中从顶到底的所有网格启动信号强化覆盖，该列中的网格将被标记为“强化覆盖”状态。

在经过若干次强化覆盖操作后，对于仍处于“未强化覆盖”状态的网格 (i, j)，如果其左侧或右侧相邻网格中至少有一个处于“强化覆盖”状态，那么该网格的信号将得到利用，其 grid[i][j] 的值会被计入总效益。

请你计算通过任意次优化操作后，该区域能够达到的最大总效益。

输入格式

第一行输入一个整数 n。

接下来 n 行，每行输入 n 个整数，表示网格中的元素值。

输出格式

输出一个整数，表示最大总效益。

数据范围

1 <= n <= 100

0 <= grid[i][j] <= 10^9

样例 1

输入

5
0 0 0 0 0
0 0 3 0 0
0 1 0 0 0
5 0 0 3 0
0 0 0 0 2

输出

11