家の区画の左上の行と列、および右下の行を決めると、支払うコストは右下の列に対して単調です。したがって、右下の列の値を二分探索することでこの問題を \(O(H^2 W \log W)\) で解くことができます。