生產線 (APCS 2021-11 中高級)

有 \(n\) 台機器排成一直線，每一台機器都有一個數值 \(t_i\)，代表該台機器要產出一單位的資料需要 \(t_i\) 單位的時間。

接下來有 \(m\) 個工作要完成，每一個工作都需要位置在 \([l_i, r_i]\) 的機器各生產出 \(w_i\) 單位資料。

現在你可以調換 \(n\) 台機器的順序，目標是使得這 \(m\) 個工作做完的總時間最小。

輸入格式

第一行有兩個正整數 \(n\) 和 \(m\)，代表有 \(n\) 台機器和 \(m\) 個工作。

接下來有 \(m\) 行，每行有三個正整數 \(l_i\)、\(r_i\) 和 \(w_i\)，代表第 \(i\) 個工作需要位置從 \(l_i\) 到 \(r_i\) 的機器完成，並且需要各產生出 \(w_i\) 單位的資料。

最後一行包含 \(n\) 個正整數 \(t_1, t_2, \ldots, t_n\)。

• \(1 \le n, m \le 200000\)
• \(1 \le w_i \le 100\)
• \(1 \le t_i \le 100\)
• \(1 \le l_i \le r_i \le n\)

輸出格式

輸出最小的總花費時間。

評分說明

• 30 分：\(1 \le n, m \le 100\)，\(w_i = 1\)
• 30 分：\(w_i = 1\)
• 40 分：無額外限制

範例輸入 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

題目來源

APCS 2021 年 11 月實作題第 3 題。

題敘參考 ZeroJudge g597「生產線」 整理，細節可能與正式試題有出入。