No.021 C

建物を増築していくとき, 現在の増築費用が最も安い建物を選んで増築していくのが合計最小にする方法である.

このとき, 最後に増築したときの費用を $V$ として, 建物 $i$ で $j$ 番目の増築に使った費用を $v_{i,j}$ すると, $v_{i,j} \leq V$ となる $i, j$ はすべて増築しているはずなので, $V$ が決まれば増築回数がわかることになる.

あとは $V$ を二分探索で探せばいい.