问题文

$N\times N$ 方格棋盘和$B$种多米诺骨牌。将左上角的方格坐标表示为$(0, 0)$，从那里向下移动$i$个方格，向右移动$j$个方格后的方格坐标被定义为$(i, j)$。初始状态下，所有的方格都是不可通过的，将多米诺骨牌放置在棋盘上会使得其上方格可通过。棋盘上有$K$个方格上有印记，并希望通过放置多米诺骨牌使得所有带有印记的方格连通。

例如，在上图中，左上角的印记与右上角的印记是连通的，但与底部的印记不连通。

可以任意数量地放置相同类型的多米诺骨牌，但不能旋转或者将其放置在棋盘之外。此外，不能将两个或更多的多米诺骨牌堆叠在同一个方格上。对于每种多米诺骨牌类型$b$，有一个成本$C_b$，当放置$m_b$个多米诺骨牌$b$时，总成本为$\\sum_{b=1}^B C_b m_b$。希望以尽可能小的总成本使得所有带有印记的方格连通起来。

得分

假设总成本为$S$，可以获得得分$\\mathrm{round}(10^8 / S)$。如果输出无效（带有印记的方格未连通、多米诺骨牌超出棋盘范围或重叠），则判定为WA。