e082. P-5-6. 線性函數(同 Q-3-14，分治版) - 花中程式設計挑戰系統

Content

有 N 線性函數fi(x) = aix + bi，1 <= i <= N。定義F(x) = max fi(x) 。輸入 c[i], 1 <= i <= m，請計算F(c[1]) + F(c[2]) + ... + F(c[m])。

Time limit: 1 秒

Input

第一行是 N 與 m。接下來有 N 行，依序每行兩個整數 ai與 bi，最後一行有 m 個整數 c[1], c[2], …, c[m]。每一行的相鄰數字間以空白隔開。N≤1e5， m≤5e4，輸入整數絕對值不超過 1e8，答案絕對值不超過 1e15。

Output

計算結果。

Sample Input

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

Sample Output

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

分治

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」