各鉄道について独立に考えれば良いです。ある鉄道 \(i\) に全部で \(t\) 回乗り、そのうち \(x\) 回で紙の切符を使うとき、その部分の運賃 \(cost_i(x)\) は \[cost_i(x) = \begin{cases} xA_i+(t-x)B_i+C_i=x(A_i-B_i)+(tB_i+C_i) & (x\neq t)\\ tA_i=t(A_i-B_i)+(tB_i+C_i)-C_i & (x=t) \end{cases} \] 　\(A_i\geq B_i\) のとき、\(x\neq t\) で \(cost_i(x)\) は \(x=t-1\) のとき最小値を取り、これは \(cost_i(t)\) より大きいです。また \(A_i<B_i\) のとき、\(x\neq t\) で \(cost_i(x)\) は \(x=0\) のとき最小値を取ります。したがって、いずれにせよ鉄道 \(i\) に支払うべき運賃の最小値は以下で与えられます。 \[ \min(cost_i(0),cost_i(t))=\min(tA_i,tB_i+C_i) \] 　あとは各鉄道について \(t\) を計算すればよいですが、愚直に実行すると \(O(MN)\) となり、小課題3はクリアできません。いくつかの区間全体に \(1\) を足す操作を高速に行えばよいのですから、これは累積和(いわゆるimos法)によって \(O(M+N)\) で実行できます。逆向きに鉄道を利用する場合に気を付けてください。

　以上より、全体の問題は \(O(M+N)\) で解けました。

C++による実装例はこちら
Perlによる実装例はこちら