\(\max \{ a_i+b_ix \}\) は下に凸なグラフとなり, 逆に \(\min \{ a_i + b_ix \}\) は上に凸なグラフとなる. よって, \(f(x)\) は下に凸なグラフとなるので, \(f(x+1) - f(x) \geq 0\) となるような最小の \(x\) を二分探索で探し出せばいい.

\(\max \{ a_i+b_ix \}\) および \(\min \{ a_i + b_ix \}\) の計算には Convex Hull Trick を用いる.