User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

31.8% (14/44)

Description

你是一名將領,正在攻打一座城,而你必須先攻打城牆,
城牆的樣子會長下方這樣,會有多道城牆重疊,
你想知道最厚的地方城牆厚度為多少,方便擬定策略。

城牆厚度計算方式如下,以上圖為例,
$0\sim3$ 的地方僅有厚度為 $1$ 的城牆,
$3\sim6$ 則有厚度為 $1$ 與厚度為 $2$ 的城牆重疊,因此 $3\sim6$ 的城牆厚度為 $1+2=3$ ,
$6\sim8$ 的地方僅有厚度為 $2$ 的城牆。
所以最厚的地方位於 $3\sim6$ 的位置,厚度為 $3$ 。

若有兩道城牆分別在 $0\sim3$ 及 $4\sim6$ ,則 $3\sim4$ 沒有城牆。

Input Format

第一行有一個正整數 $N\ (N\leq10^ 6)$ ,代表有幾道城牆。
接下來有 $N$ 行,每行有三個非負整數 $l,r,w\ (0\leq l<r\leq 10^ 9, 0<w \leq 10^ 5)$ ,代表有一道城牆位於 $l$ 到 $r$ (包含 $l,r$ ),厚度為 $w$ 。

Output Format

請輸出一個正整數,代表城牆最厚的地方厚度為多少。

Sample Input 1

2
0 6 1
3 8 2

Sample Output 1

3

Sample Input 2

3
0 5 3
2 9 2
6 13 3

Sample Output 2

5

Sample Input 3

3
0 5 3
2 10 2
6 13 3

Sample Output 3

5

Sample Input 4

3
0 5 1
3 7 1
5 10 1

Sample Output 4

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~6 $N\leq3\times10^ 3$ 且 $l,r\leq2\times10^ 4$ 16
2 0~13 $l,r\leq10^ 5$ 29
3 0~6, 14~20 $N\leq10^ 5$ 20
4 0~27 無特別限制 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2 3 4
1 2000 65536 65536 1 2 3 4
2 2000 65536 65536 1 2 3 4
3 2000 65536 65536 1 2 3 4
4 2000 65536 65536 1 2 3 4
5 2000 65536 65536 1 2 3 4
6 2000 65536 65536 1 2 3 4
7 2000 65536 65536 2 4
8 2000 65536 65536 2 4
9 2000 65536 65536 2 4
10 2000 65536 65536 2 4
11 2000 65536 65536 2 4
12 2000 65536 65536 2 4
13 2000 65536 65536 2 4
14 2000 65536 65536 3 4
15 2000 65536 65536 3 4
16 2000 65536 65536 3 4
17 2000 65536 65536 3 4
18 2000 65536 65536 3 4
19 2000 65536 65536 3 4
20 2000 65536 65536 3 4
21 2000 65536 65536 4
22 2000 65536 65536 4
23 2000 65536 65536 4
24 2000 65536 65536 4
25 2000 65536 65536 4
26 2000 65536 65536 4
27 2000 65536 65536 4