Room

A simple polygon in the plane is monotone if every vertical line meets the interior of the polygon in at most one line segment, and it is orthogonal if every edge of the polygon is horizontal or vertical. Room outlines in floor plans are often orthogonal and monotone, so a room is represented by an orthogonal monotone polygon in the plane.

Reconstruct the polygon from a set of data points measured on the outline of an orthogonal monotone room. The interior of the room is connected. Every edge of the outline carries exactly one data point, and that point lies in the interior of the edge. Each data point consists of its position (the x coordinate and the y coordinate) and the orientation of the edge it lies on. The orientation is H for a horizontal edge and V for a vertical edge. Compute the length of the boundary of the orthogonal monotone polygon reconstructed from the set of data points.

Figure 1. 12 data points in the plane: (9, 1, H), (3, 5, H), (6, 6, V), (5, 7, H), (14, 7, V), (11, 3, V), (7, 5, H), (13, 10, H), (12, 6, H), (1, 6, V), (4, 4, V), (8, 7, V).

Suppose the 12 data points of Figure 1 are given. Each data point is drawn as a point together with a short segment that gives the orientation of the edge it lies on. From these data points you can reconstruct the orthogonal monotone polygon of Figure 2. No polygon other than the one in Figure 2 can be reconstructed from these data points.

Figure 2. The orthogonal monotone polygon reconstructed from the data points of Figure 1.

The polygon in Figure 2 consists of edges of lengths 2, 5, 2, 2, 5, 6, 4, 3, 5, 7, 4, 3 in clockwise order along the boundary, starting from the leftmost vertical edge. So when the 12 data points of Figure 1 are given as input, the answer is 48.

The first line contains the number of data points $n$ ($4 \le n \le 500\,000$). Each of the next $n$ lines contains one data point: its x coordinate, its y coordinate, and an indicator of 0 or 1 that gives the orientation. Each coordinate is an integer between $-2^{30}$ and $2^{30}-1$, inclusive. The indicator is 0 if the edge carrying the data point is horizontal, and 1 if it is vertical.

Print the length of the boundary of the orthogonal monotone polygon reconstructed from the input. If no orthogonal monotone polygon can be reconstructed from the input, print -1.