時間限制 3000 ms ・ 記憶體限制 512 MB
題目描述
N 台機器分別有每單位資料的製作時間 t。M 項工作各指定位置區間 [l,r]，區間內每個位置的機器都必須製作 w 單位資料。可以在執行工作前任意排列機器。總時間定義為每台機器製作各項所需資料的時間總和，請找出其最小值。
輸入格式
第一行為 N、M，皆介於 1 與 200000。接著 M 行為 l、r、w，滿足 1 ≤ l ≤ r ≤ N，1 ≤ w ≤ 100。最後一行為 N 個 t 值，皆介於 1 與 100。
輸出格式
輸出可達成的最小總時間。
範例測資
範例輸入 1
5 1 2 4 1 1 2 3 4 5
範例輸出 1
6
範例輸入 2
10 3 2 5 6 3 6 4 7 8 1 1 2 3 4 5 6 7 8 9 10
範例輸出 2
117
請先登入後再提交程式碼
討論與題解
載入討論區…