Problem : 339 - pC.呂雷可愛電墊子

Problem Statistics

Solved Member: 16　　Submission: 52　　User Tried: 18

Statement:

最近吉汁社發明了一種吸收電力的墊子，每吸收1電力會膨脹1單位的厚度。
呂雷可因為自己電太多了，所以決定買了一長串的墊子來電。每次都會選擇一段連續的區間來電，每次釋放的電力皆平均分佈在各點，隨著呂雷可一次次的放電，墊子也日漸變厚，最後上了報紙，還成為了附中知名景點，為了紀念這一件偉大的事蹟，要在最厚的地方標上厚度。但是墊子實在太厚導致太難測量，幸好呂雷可有記錄下每次電的區間跟施放的電力，不過由於次數太多需要你的幫助，請你幫他計算最後的墊子到底有多厚。

Input:Output:

第1行有兩個數字N,M，N代表這一個墊子有N的長度，M代表鋁類科總共電了幾次
第2~M+1行每行有三個數字Li,Ri,Ki,代表呂雷可第i次從Li滾到Ri，途中每個墊子皆接受到 Ki 單位的電力

N,M<1000000
1<=Li,Ri<=N
0<=Ki<=100

請輸出墊子最厚的厚度

Sample Input:Sample Output:

10 5
2 3 95
5 9 19
8 8 56
7 7 7
2 5 64

159

HINT:

N,M<1000000
1<=Li,Ri<=N
0<=Ki<=100

Source:

103附中校內賽

Problem Setter

IPJ

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1-1	1000ms	262144kb	20
1-2	1000ms	262144kb
2-1	1000ms	262144kb	20
2-2	1000ms	262144kb
3-1	1000ms	262144kb	20
3-2	1000ms	262144kb
4-1	1000ms	262144kb	20
4-2	1000ms	262144kb
5-1	1000ms	262144kb	20
5-2	1000ms	262144kb