The Shadow

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

When this semester is over, fish-head feels extremely sorry about the oldest teammates’ leaving. So he gathered all the teamers, went out for photos. Sunsets beautifully shone at the horizon and all the teamers stood in line and got lost in the scene. Fish-head suddenly found the shadow of teamers was kind of funny. All the teamers were so strong that their shadow almost became rectangle! Now fish-head wants to know how much the area of the shadow down there. Everyone’s shadow is lined up straight towards the sun so we just regard it as a line and each shadow as rectangle. Each rectangle has 3 parameters: Ai, Bi, Hi. The shadow begins with Ai (point), ends with Bi (point), and its height is Hi.

Input

Line 1: A single integer: N(1 ≤ N ≤ 40,000) represents the number of teamers. Lines 2..N+1: Input line i+1 describes shadow i with three space-separated integers: Ai, Bi, (1 ≤ Ai < Bi ≤ 1,000,000,000) and Hi(1 ≤ Hi ≤ 1,000,000,000).

Output

Line 1: The total area, in square units, of the pattern formed by all N teamers’ shadow.

Sample Input

4
2 5 1
9 10 4
6 8 2
4 6 3

Sample Output

16

Hint

Source

JiaQiong

提交代码