隨著[串一串脆薯]的生意越來越好，全國的人都搶著要買，甚至不惜犧牲寶貴的午餐時間頂著大太陽排隊

某天有\(n\)個人在[串一串脆薯店]排隊買脆薯，第\(1\)個人的編號是\(1\)，第二個人是\(2\), \(...\)依此類推。

老闆娘看大家站在太陽底下排隊很辛苦，於是決定給他們\(t\)次大放送:

第\(i\)次大放送老闆娘會選兩個整數\(a_i, b_i\)，並免費送編號\(a_i, a_{i+1}, ..., b_i\)的人\(x_i\)根脆薯

假設這\(n\)個人都很有耐心等待老闆娘執行完\(t\)次大放送並且結束後編號\(i\)的人會買\(c_i\)根脆薯

請計算大放送結束且這\(n\)個人都買到他們要買的脆薯後，得到最多根脆薯的人有幾根。

\(1 \le n, t \le 10^6\)
\(1 \le a_i \le b_i \le n\)
\(0 \le x_i, c_i \le 1000\)

輸入說明

第一行有兩個數\(n, t\)
第二行有\(n\)個數 \(c_1, c_2, ..., c_n\)
接下來有\(t\)行其中的第\(i\)行有三個數 \(a_i, b_i, x_i\)

輸出說明

輸出得到最多跟脆薯的人的脆薯數

範例輸入

5 3
1 2 2 1 5
1 3 5
2 5 1
1 5 9

範例輸出

17

範例說明

所有人原本都沒有脆薯。
脆薯數: \(0\ 0\ 0\ 0\ 0\)
第一次大放送給編號1到3的人一人5根脆薯
脆薯數: \(5\ 5\ 5\ 0\ 0\)
第二次大放送給編號2到5的人一人1根脆薯
脆薯數: \(5\ 6\ 6\ 1\ 1\)
第三次大放送給編號1到5的人一人9根脆薯
脆薯數: \(14\ 15\ 15\ 10\ 10\)
大放送結束後所有人分別購買 \(1\ 2\ 2\ 1\ 5\) 根脆薯
脆薯數: \(15\ 17\ 17\ 11\ 15\)
擁有最多脆薯的人有\(17\)根，故輸出\(17\)

子題配分