406587: GYM102448 F Finally, christmas!

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Finally, christmas!time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The christmas spirit is taking over the city of Arcoverde! In honor of this special day, the mayor of this renowned metropolis decided to decorate all of the city's front view. To do this, he asked his engineer friends Icaro and Cortizo how much it would cost.

It is known that the mayor likes to save as much money as possible. Therefore, Icaro and Cortizo need to find out what is the minimum area necessary to comprise the entire city's front view.

Arcoverde is made only of rectangular buildings, in two dimensions, and all buildings were built on the same base height, as shown on the picture below.

Icaro and Cortizo were very tired, since they were also responsible for building the biggest christmas tree ever seen on Pernambuco, so they asked for your help.

Input

The first input line contains an integer $$$N$$$($$$1 \le N \le 10^{5}$$$), indicating the number of buildings in Arcoverde. Then, $$$N$$$ lines follow, each one containing three integers $$$L_i$$$ ($$$0 \le L_i < 10^{9}$$$), $$$R_i$$$ ($$$L_i < R_i \le 10^{9}$$$) and $$$H_i$$$ ($$$1 \le H_i \le 10^{6}$$$), which are, respectively, the left X-coordinate, the right X-coordinate and the height of the $$$i$$$-th building.

Output

The output consists in a single integer number, which is the minimum area required to decorate the entire front view of Arcoverde.

ExampleInput
6
2 6 9
9 14 11
12 20 6
17 25 20
23 31 14
29 36 18
Output
451

加入题单

上一题 下一题 算法标签: