问题文

A,B,C的三个问题只有测试用例的数量和输入生成方法不同。

### 问题文

一个大小为 N×N 的棋盘和 B 种类的多米诺骨牌。将左上角的方格坐标定义为 (0, 0)，从该方格向下移动 i 个方格，向右移动 j 个方格后到达的方格坐标为 (i, j)。初始状态下，所有方格都是不可通行的，将多米诺骨牌放置在棋盘上会使其上方格变为可通行状态。在棋盘上有 K 个标记方格，希望通过放置多米诺骨牌使得所有标记方格连通。

![](https://img.atcoder.jp/future-fif-digital-days/b490bb01158a72323fc4b1072acff8ef.svg)

例如，上图中，左上角的标记和右上角的标记是连通的，但与下方的标记不连通。

可以任意放置相同类型的多米诺骨牌，但不能旋转或超出棋盘范围放置。同时，不能在一个方格上叠放两个或更多的多米诺骨牌。每个多米诺骨牌的类型 b 对应一个成本 C_b，当放置了 m_b 个类型为 b 的多米诺骨牌时，总成本为 \\sum_{b=1}^B C_b m_b。希望以尽可能小的总成本使得所有标记方格连通。

### 得分

假设总成本为 S，则得分为 round(10^8 / S)。如果输出是非法的（标记方格未连通、多米诺骨牌超出棋盘范围或重叠），则判定为 WA（错误回答）。