本题没有可用的提交语言。

题目描述

给定一个 $N \times N$ 的矩阵 $A$，其中的元素均为不超过 $10000$ 的正整数。矩阵中还有一些 '*'。你的任务是找到三个（可以重叠的）矩形，使得这三个矩形能够覆盖矩阵中所有的 '*'，并且每个矩形的面积（定义为该矩形覆盖的元素个数）不超过给定的整数 $M$。

如果存在多个解，程序应选择总成本最小的解。其中，单个矩形的成本定义为该矩形覆盖的所有元素之和。

输入格式

第一行是一个整数 $X$，表示测试用例的数量。接下来的 $X$ 个块，每个块表示一个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 30$，$0 \leq M \leq N \times N$），分别表示矩阵的大小和每个矩形的最大允许面积。第二行是一个整数 $C$（$0 \leq C \leq N \times N$），表示矩阵中 '*' 的数量。接下来的 $C$ 行，每行包含两个整数 $X$ 和 $Y$（$1 \leq X, Y \leq N$），表示矩阵中第 $X$ 行第 $Y$ 列的元素为 '*'。接下来的 $N$ 行，每行包含 $N$ 个整数，表示矩阵 $A$。

输出格式

对于每个测试用例，输出一行。如果存在满足条件的解，输出最小总成本；否则输出 Impossible。

输入样例 1

5
1 1
0
9
1 1
1
1 1
9
5 6
5
1 1
3 4
4 3
4 5
5 4
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1
5 3
5
1 1
3 4
4 3
4 5
5 4
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1
5 2
4
1 1
3 4
4 3
4 5
5 3 1 1 1
3 1 1 1 1
1 1 1 2 1
1 1 2 5 2
1 1 1 2 1

输出样例 1

0
9
20
23
Impossible

来源

POJ Monthly--2005.07.31, LouTianCheng