魔法城堡

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

俊吉主任(簡稱鈞任)是一位熱愛海洋的8+9,家裡擁有許多的小島,而且從小時候就非常喜愛魔法城堡,而長大成人的他現在是一位土木工程師。
他想要著手建造他所夢想的魔法城堡。但是由於經費不足,鈞任想出一套解決辦法:
在海洋上規劃一個旅行,船從小島1出發,依序經過小島2, 3, ... n-1,最後到達小島n,在每個小島,民眾可以選擇在此小島上船或是下船。
後來他發現他的客戶跟「日本進口壓縮機」一樣稀少,所以他打算統計從小島i到j途中船上人數的最大值\((1 <= i, j <= n, i < j)\),以便調整方案。


Input

輸入僅包含一筆測資。
第一列有1個正整數\(n\)代表小島數量。
第二列有一個正整數\(m\),代表有m筆乘客資訊。
接下來有\(m\)列,每列包含\(i, j, k(1 <= i, j <= n, i < j)\),代表\(k\)個乘客有相同行為,都是從小島\(i\)上船,小島\(j\)下船。

Output

請輸出人數的最大值為多少
PS: 假如乘客在j島下船,則在統計人數時視為還在船上;若有乘客上船,則統計人數時會計算到上船的旅客。

Constraints

第 \(1\) 組測資, \(n\leq10^3\), \(m\leq10\)。 \((20\text{%})\)

第 \(2\) 組測資, \(n\leq10^4\), \(i+1=j\)。 \((20\text{%})\)

第 \(3\) 組測資, \(n\leq2*10^5\)。\((20\text{%})\)

第 \(4\) 組測資, \(n\leq2^{50}\)。\((40\text{%})\)

對於所有測資,\(m<=10^5\), \(k<=1000\)。

Sample Input
6
3
2 5 2
3 6 5
1 4 10
Sample Output
17

Comments

There are no comments at the moment.