TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

42.9% (6/14)

Tags

Description

APCSC 公司長期在跟 n 間敵對公司對抗,這些公司編號為 1,2,,n

APCSC 公司的老闆想調查這些敵對公司的營業額,為此,他們派了 m 個偵探去秘密調查,為了不被發現,偵探只能調查一部分的敵對公司,而且也只能問到這幾間公司營業額最大值的上限。

最後調查報告出爐,第 i 位偵探的調查結果顯示,公司 li 到公司 ri 的營業額均不超過 pi 元,其中 p1,p2,,pm 兩兩相異。

有了這些資訊,APCSC 公司的老闆想知道這 n 間敵對公司的營業額總和最大是多少?可是這位老闆不太會寫程式,所以他委託你幫他算出來。

Input Format

第一行輸入兩個正整數 n,m

接下來輸入 m 行,第 i 行輸入三個整數 li,ri,pi

  • 1n,m105
  • 1lirin
  • 1pi109
  • 保證 p1,p2,,pm 兩兩相異

Output Format

如果營業額總和沒有上限,則輸出 infinity,否則輸出一個整數,代表營業額總和的最大值。

Sample Input 1

6 4
1 2 3
4 5 2
2 6 4
3 3 8

Sample Output 1

18

Sample Input 2

10 5
1 2 4
3 4 5
6 7 3
7 9 1
9 10 100

Sample Output 2

infinity

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 n,m1000 40
3 0~16 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3