作成中
本質は https://atcoder.jp/contests/arc107/tasks/arc107_f と同じ それぞれのマスについて、塗る(+)、塗る(-)、塗らないの3状態。塗る(+)と塗る(-)が隣り合ってはいけない。
全て塗ると利得がある＝一つでも塗らないと損失(https://kanpurin.hatenablog.com/entry/moyasu-umeru#moya1ijou) 塗る(+)と塗る(-)は隣り合わないため、「一列全て塗る(+)なら利得」と「一列全て塗る(-)なら利得」だけ追加すれば良い。