题目描述

在一个 n×n 的棋盘中，每个方格都被赋予一种颜色，要么是颜色 0，要么是颜色 1。

现在需要用若干 1×2 的卡片覆盖该棋盘，覆盖需满足以下规则：

• 一张卡片必须恰好覆盖两个相邻的方格；

• 被同一张卡片覆盖的两个方格必须颜色相同；

• 卡片之间不能重叠。

请计算在上述规则下，卡片最多能覆盖的方格总数。

输入格式

1. 第 1 行包含一个整数 n，表示棋盘的边长；

2. 接下来 n 行，每行包含 n 个整数（取值为 0 或 1），依次表示棋盘对应方格的颜色。

输出格式

输出一个整数，代表卡片最多能覆盖的方格数量。

样例输入

5
0 1 1 1 0
0 1 1 0 1
1 1 0 1 1
1 1 0 1 0
0 1 0 1 1

样例输出

18

数据范围与提示

对于所有测试数据，满足 1 ≤ n ≤ 300。