### 问题描述 小齐的农田地势多变，他准备购买一台新的拖拉机用于在田地里行驶。农田被描述为一个 $N \times N$ 的方格矩阵，其中每个方格包含一个非负整数的高程值 $(0 \leq N \leq 500)$。拖拉机能够从一个方格移动到相邻的方格（向北、向东、向南、向西），而移动到高度差为 $D$ 的相邻方格会耗费 $D$ 个单位的费用。 小齐希望为拖拉机支付足够的费用，以便从田地中的某个方格出发，成功地驾驶拖拉机四处游览至少一半的方格（如果田地中的方格总数为奇数，则至少要游览至少一半的方格并向上取整）。请帮助他计算购买满足此要求的拖拉机的最低费用。 ### 输入格式 第 $1$ 行：整数 $N$ 的值。 接下来 $N$ 行：每行包含 $N$ 个非负整数（每个整数最大为一百万），指定了小齐的农田中的一行。 ### 输出格式 能够在小齐的农田中至少游览一半方格的最低费用。 ### 样例输入 ``` 5 0 0 0 3 3 0 0 0 0 3 0 9 9 3 3 9 9 9 3 3 9 9 9 9 3 ``` ### 样例输出 ``` 3 ``` ### 评测数据规模 $0 \leq N \leq 500$。