随着时间的推移，人们开始通过记录来保存他们的文明。在石板上，他们刻下了代表他们的村庄、仪式、变迁和历史的数字。
但多年以后，他们发现这些记录的一些部分存在缺陷。为了恢复正确的顺序，他们着手纠正这些错误。
检查他们留下的记录，并恢复失去的历史轨迹。
记录呈现为一个 $N \times N$ 的网格。从上往下数第 $r$ 行、从左往右数第 $c$ 列的单元格记为 $(r, c)$。每一行代表一个 $N$ 位数，从左到右书写，每个单元格中有一个数字。
根据预期的结构，各行的值——当从左到右读作数字时——应该从上到下严格递增。然而，由于抄写错误，一些数字可能被错误地记录了，导致某些行不再遵循这种递增顺序。
为了纠正记录，人们决定从网格中擦除一些数字。他们的目标是确保每一行中剩余数字（从左到右阅读）所组成的数字从最上面一行到最下面一行严格递增。
例如，考虑下图所示的情况：
通过擦除如图所示的六个数字，剩余的数字变为 $[335, 854, 2198, 7356, 26481]$。这些值从一行到下一行严格递增，符合预期。
确定必须擦除的最小数字个数。
输入格式
第一行包含一个整数 $N$ —— 石板的大小。
接下来的 $N$ 行，每行包含一个长度为 $N$ 的数字字符串 $B_{i1}, B_{i2}, \dots, B_{iN}$。$B_{ij}$ 是记录在单元格 $(i, j)$ 中的数字。
数据范围
- $2 \le N \le 2000$
- $1 \le B_{ij} \le 9$ ($1 \le i, j \le N$)
输出格式
输出必须擦除的最小数字个数。
保证总是可以通过擦除零个或多个数字来满足条件。
子任务
- 子任务 1（3 分）：$B_{ij} = 1$ ($1 \le i \le N, 1 \le j \le N$)
- 子任务 2（8 分）：$N \le 4$
- 子任务 3（18 分）：$N \le 15$
- 子任务 4（21 分）：$N \le 100$
- 子任务 5（22 分）：$N \le 500$
- 子任务 6（28 分）：无附加限制。
样例
输入样例 1
5 33645 86541 42198 79356 26481
输出样例 1
6
输入样例 2
3 111 111 111
输出样例 2
3
输入样例 3
8 19283746 85749285 56748236 17846565 77759471 85625624 41837461 23876597
输出样例 3
13