题目描述

在一个 $n\times n$ 的棋盘中，每个方格都有颜色：要么是颜色 $0$ ，要么是颜色 $1$。
用一些 $1\times 2$ 的卡片覆盖棋盘，要求一张卡片要正好覆相邻且同色的正常方格，卡片不能重叠。
试求：在上述规则下，卡片最多能覆盖多少方格。

输入格式

第 $1$ 行有一个整数 $n$，表示棋盘边长。
在接下来的 $n$ 行中，每行有 $n$ 个数，表示棋盘颜色。

输出格式

输出一个整数，表示能覆盖多少方格。

样例

input

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

output

18

数据范围与提示

$1≤n≤300$。