Sum of Linear Functions

$f_{a,b}\colon \mathbb {R} \to \mathbb {R} ;\ x\mapsto f_{a,b}(x)=ax+b$ という写像（一次関数）における，"$+$"という演算を仮に以下のように定める．

$f_{a,b} + f_{c,d} = f_{a+c,b+d}$

この時，写像$f_{a,b}$の集合は2項演算"$+$"に関して閉じている． つまり，一次関数の集合において，上の"$+$"演算をした結果もまた一次関数であるということです．

また，同時に以下の事実にも気づきます．

この写像における2項演算"$+$"は，可換群である．

ここで，与えられる一次関数を全て"$+$"した後の関数について考察を深めましょう．その関数のグラフは，係数が異なる一次関数が連続？したグラフになります．
$f$を一次関数としたとき，$a \leq x \leq b$における$f(x)$の最大値は$f(a)$か$f(b)$のどちらかなので，一次関数の係数が変化する座標のみが答えの候補となることがわかります．

以上の考察より，imos法により，与えられる一次関数を全て"$+$"した後の関数を作り，一次関数の係数が変化する座標でのみ嬉しさの合計を求め，その最大値を求めることで，$\mathrm{O}(N)$で答えを得ることができます．