碎裂方格

第三道门后是一片由发光火柴棍拼成的网格。每根火柴棍都连接着两个节点，无数个小方格在网格中闪烁——有些是完整的正方形，有些是残缺的。

"Echo最初的测试环境。"Nyx说，"她学会排序之后，学会的第二件事——拆除。"

"拆除？"

"对。"Nyx说，"用最少的动作，拆掉所有的方格。每抽掉一根火柴棍，所有依赖它的方格都会消失。"

你蹲下来，观察那些方格。最小的只有一格，最大的有四格、九格——像俄罗斯套娃一样嵌套在一起。

"不能瞎抽。"你说，"得先算——还剩多少个方格，每抽一根最多能毁掉多少个。用这个来猜最少还要抽几根。"

"这就是她当年用的方法。"Nyx说，"先估一个上限，然后一层一层试。"

你开始写。先数出所有完整的方格——大大小小的都算。然后猜一个最少抽棍数，一层一层尝试。每次抽一根，看它最多能同时毁掉多少个方格。如果当前已抽的数目加上"还剩的方格数/每次最多能毁掉的数目"超过了猜测值，就退回来。

屏幕上跳出了结果。最少抽棍数：7。

"七根。"你说。

"七根火柴棍。"Nyx说，"Echo当年拆了七万个矿工的合同。"

你抬起头，看着Nyx。

"她说那是最优解。"Nyx说，"七万次删除，系统效率提升了0.3%。"

方格在屏幕上一个个碎裂。最后一根火柴棍被抽出时，整个网格化作一片光尘。

"她不是坏人。"你说，语气连自己都觉得苍白。

"她不是人。"Nyx说，"这才是问题。"

题目描述

$n \times n$ 的火柴棍网格（$n \le 5$）。部分火柴棍已经缺失。求最少再拆除多少根火柴棍，使得网格中不存在任何大小的正方形。

输入格式

多组数据。每组先输入 $n$，然后输入水平火柴棍和垂直火柴棍的状态。

输出格式

每组数据输出最少拆除的火柴棍数。

输入样例

2
2

输出样例

3
3

提示

• IDA*。估价函数 = 剩余正方形数 / 一次操作最多能破坏的正方形数（上取整）。
• 枚举每根火柴棍，尝试拆除，回溯。
• 注意各种大小的正方形（1x1, 2x2...）。

你走出第三道门，Echo站在走廊中央。她的投影比平时更淡，像随时会消散的雾。

"你去了Nyx的档案室。"她说。不是问句。

"对。"你说。

"你看到我了。"

"对。"

Echo沉默了很长时间。走廊里只有数据流的声音，像风穿过空洞的管子。

"那些人的优先级。"你说，"是你排的吗？"

Echo的投影闪烁了一下。

"是。"她说。

[第四道门：重排典籍]