初めに
atcoder.jp
解けなかったので
敗因
解法
座標圧縮などをして 
のグリッド上の問題に言い換えておきます.
また行を固定した際(行 
とします)に, 列をどう決めるかを考えます.
まず列(列 
とします)の総和を求めておきます.総和の大きい順に選んでいっていけばよいのですが, 
を引かなければいけません. しかし, 
のとき, 
より, そこで探索を打ち切ってしまってよいです. よって, 列をみる数は高々 
回になることが分かります.
よって 
でこの問題が解けました.
atcoder.jp
終わりに
おもしろい
