A6129. 「USACO 2019 US Open Platinum」Compound Escape
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2019 US Open Contest, Platinum](http://usaco.org/index.php?page=open19results) Problem 2. [Compound Escape](http://usaco.org/index.php?page=viewproblem2&cpid=949)**
Bessie 和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是 Bessie 站出来策划脱逃的时候了！这一房屋包含 $NK$ 个排列成 $N\times K$ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。
Bessie 黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie 必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie 想要使得总的解锁花费最小。
但是这次行动异常关键，Bessie 不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。
由于这个数字可能非常大，只需输出该数对 $10^9+7$ 取模的余数。
Bessie 和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是 Bessie 站出来策划脱逃的时候了！这一房屋包含 $NK$ 个排列成 $N\times K$ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。
Bessie 黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie 必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie 想要使得总的解锁花费最小。
但是这次行动异常关键，Bessie 不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。
由于这个数字可能非常大，只需输出该数对 $10^9+7$ 取模的余数。
输入格式
输入的第一行包含两个空格分隔的整数 $N$ 和 $K$（$2\le N\le 3\cdot 10^4,2\le K\le 6$）。
以下 $N$ 行每行包含 $K-1$ 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。
以下 $K$ 行每行包含 $N-1$ 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。
所有的花费均在 $1$ 到 $10^9$ 之间。
以下 $N$ 行每行包含 $K-1$ 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。
以下 $K$ 行每行包含 $N-1$ 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。
所有的花费均在 $1$ 到 $10^9$ 之间。
输出格式
一个整数：最小花费的逃脱方案的数量，对 $10^9+7$ 取模。
输入输出样例
输入 #1
4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1
输出 #1
10
说明/提示
对于 $20\%$ 的测试数据，保证 $N\le 500$，所有的代价均在 $1$ 到 $5$ 之间。
对于另外 $20\%$ 的测试数据，保证 $N\le 5\cdot 10^3$。
对于另外 $20\%$ 的测试数据，保证 $N\le 5\cdot 10^3$。