線性函數 (AP325 Q-3-14)

有 \(N\) 個線性函數 \(f_i(x) = a_i x + b_i\)，\(1 \le i \le N\)。定義 \(F(x) = \max_i f_i(x)\)。輸入 \(c[i]\)，\(1 \le i \le m\)，請計算 \(\sum_{i=1}^{m} F(c[i])\)。

輸入格式

第一行是 \(N\) 與 \(m\)。接下來有 \(N\) 行，依序每行兩個整數 \(a_i\) 與 \(b_i\)，最後一行有 \(m\) 個整數 \(c[1], c[2], \ldots, c[m]\)。每一行的相鄰數字間以空白隔開。

限制

• \(1 \le N \le 10^5\)，\(1 \le m \le 5 \times 10^4\)。
• 輸入整數絕對值不超過 \(10^8\)。
• 答案絕對值不超過 \(10^{15}\)。
• 不同的函數可能有相同的斜率 \(a_i\)，也可能完全相同。

輸出格式

計算結果。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

4 5
-1 0
1 0
-2 -3
2 -3
4 -5 -1 0 2

範例輸出

15

範例說明

\(F(4) = 5\)、\(F(-5) = 7\)、\(F(-1) = 1\)、\(F(0) = 0\)、\(F(2) = 2\)，總和 \(15\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 3 章 Q-3-14，第 106 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。