\(2\) 個からなるサンドイッチの一方を小サンドイッチと呼びます．

あるサンドイッチについてどちらの小サンドイッチを最初にとるか決めた時，とるべきサンドイッチの集合は一意に定まります．よって，取るのに必要な小サンドイッチが少ないサンドイッチから答えを確定させていくとしてもよいです．

ある小サンドイッチ \(X\) を取るのに必要な小サンドイッチの集合は斜辺に接する小サンドイッチを取るための集合に \(X\) を加えたものか，斜辺以外で接する小サンドイッチを取るための集合の和に \(X\) を加えたものです．後者の処理ができればおおよそかまいません．

後者は集合の和なので \(RC\) 個のbitを持ったbitsetによる高速化ができます．集合をマージする回数は \(O(RC)\) 回なのでワードサイズを \(w\) として，計算量は \(O(\frac{(RC)^2}{w}) \fallingdotseq 4 \times 10^8\) となり，bit演算が軽い処理であること, TL が \(5\) 秒であることを踏まえれば十分間に合います．

問題なのはメモリです．愚直に持つと \((RC)^2 \fallingdotseq 3000 \mathrm{MB}\) ほどになります．しかし，「集合のマージにもう使われないサンドイッチについての情報を削除する．」という処理を行うことによって省メモリになることが期待され，正解することができます．（筆者はこの予想についてなにも証明を行っていません．もしかしたらHack可能なケースがあるかもしれませんが，少なくとも現在存在するケースに対しては正解できます．証明されたようです ．ありがとうございます．）