G. windowmanager
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bill is developing a window manager for his new operating system.

The scene consists of $$$n$$$ rectangles. All windows have distinct integer $$$z$$$ coordinates. If windows overlap, the one with greater $$$z$$$ coordinates is on top. When drawing the scene, for each window, you only draw the part of it which is on top of all other windows. It turns out that the most time-consuming operation is drawing the borders of the windows.

Bill defines scene complexity as the minimum number of segments that need to be drawn for all the visible window borders. For example, in the following scene:

You need to draw 19 segments: 11 horizontal and 8 vertical ones.

Your task is, given the description of the windows, to calculate how many segments the window manager needs to draw.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of windows.

The following $$$n$$$ lines describe the windows. Each line contains five integers: $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, $$$z$$$ — coordinates of the bottom-left and the top-right corners, and the $$$z$$$-coordinate of the window. ($$$0\le x_1 \lt x_2\le 1000$$$, $$$0\le y_1 \lt y_2\le 1000$$$, $$$1\le z\le n$$$, all $$$z$$$ are distinct).

Output

Output one integer, the minimum number of segments that need to be drawn for all the visible window borders.

Example
Input
5
6 4 7 8 4
10 5 12 6 5
3 2 8 7 1
5 1 10 5 2
2 3 3 5 3
Output
19