Li Chao Tree による \(O(M\log^2N)\) 解法です．

簡単のため所持金を \(0\) 円から始め，負になることも許すものとします．

また \(1\) 回目の市場が行われる前と，市場に参加した後にのみ移動できるとして構いません．

\(i\) 回目の市場が行われた後に（必要ならば移動して）街 \(j\) にいるときの所持金の最大値を \(f_i(j)\) とします．

このとき \(f_0(x)=-C|x-1|\)，また \(i=1,\dots,M\) に対し

\[\begin{aligned} f_i(x) &=\max(f_{i-1}(x),f_{i-1}(T_i)+P_i-C|x-T_i|)\\ &=\begin{cases} \max(f_{i-1}(x),Cx-CT_i+f_{i-1}(T_i)+P_i)&(x\lt T_i)\\ \max(f_{i-1}(x),-Cx+CT_i+f_{i-1}(T_i)+P_i)&(x\geq T_i) \end{cases} \end{aligned}\]

が成り立ちます．

線分追加に対応した Li Chao Tree を用いればこの式をそのまま実装でき，計算量は \(O(M\log^2N)\) になります．