No.026 D

時給が $S$ に決まると, 各道を作るための予算が $ST_i$ に決まる. そうすると道ごとに予算の過不足 $x_i = C_i - ST_i$ がでる. (プラスが不足, マイナスが過剰)

$x_i \lt 0$ の場合は無条件に道を引く.

そうでない場合は $\sum x_i$ をできるだけ小さくして全域木を作ったときに予算が不足しないかどうかを見ればいいので, 最小全域木の問題になる.

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