A,B,Cの3つの問題はテストケース数と入力の生成方法のみが異なります。

問題文

$N\\times N$ マスの盤面と $B$ 種類のポリオミノがある。 一番左上のマスの座標を $(0, 0)$ とし、そこから下へ $i$ マス、右へ $j$ マス移動した先のマスの座標を $(i, j)$ と定める。 初期状態で全てのマスは通行不能であり、ポリオミノを盤面に配置するとその上が通行可能になる。 盤面上の $K$ 個のマスに印が付いており、ポリオミノを配置することで全ての印が付けられたマスが連結になるようにしたい。

例えば、上の図では左上の印と右上の印は連結になっているが、下の印とは連結になっていない。

同一種類のポリオミノを任意個配置することが出来るが、回転させたり、盤面からはみ出すように配置することは出来ない。 また、1つのマスの上に2つ以上のポリオミノを重ねて配置することも出来ない。 各ポリオミノの種類 $b$ ごとにコスト $C_b$ が定まっており、ポリオミノ $b$ を $m_b$ 個配置したとき、合計コストは $\\sum_{b=1}^B C_b m_b$ となる。 出来るだけ小さい合計コストで全ての印が付けられたマスを連結にしてほしい。

得点

合計コストを $S$ とすると、$\\mathrm{round}(10^8 / S)$ の得点が得られる。 不正な出力(印のついたマスが連結になっていない、ポリオミノが盤面からはみ出している、もしくは重なっている)がされた場合、WA