解题思路

把 n×n 的网格按列看：一次“优化操作”会把某一整列标记为“强化覆盖”。 最后统计规则：未被选中的列，只要与其相邻（左或右）有被选中的列，则这一整列所有格子的数值都会计入总效益；被选中的列本身不计入。

因此，可把每一列的权值设为该列元素之和 w[j] = Σ_i grid[i][j]。问题转化为：

在长度为 n 的路径图（1…n）上，选择若干个点 S，使得未被选中的且与 S 相邻的点的权值和最大。 （被选中的点自身不计入。）

题目内容

某区域被划分为$n×n$的网格区域，用于部署$5G$网络。初始时，所有网格都处于信号未强化覆盖状态。网络工程师可以执行任意次优化操作:选择任意一个网络格，对第$i$列中从顶到底的所有网络格启动信号强化覆盖，该网络格将被标记为“强化覆盖”状态。

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

请编写代码返回通过任意次优化操作后，该区域能达到的最大总效益。

输入描述

第一行输入一个整数，表示$n$。

后$n$行每行输入$n$个整数，表示$grid$。

输出描述

一个整数，表示通过任意次优化操作后，该区域能达到的最大总效益。

样例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

提示

$1 <= n == grid.length <=100$

$n = grid[i].length$

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