방

평면 위의 단순 다각형에서 모든 수직선이 다각형 내부와 만나는 부분이 많아야 선분 하나이면 그 다각형을 단조라고 한다. 모든 변이 수평이거나 수직이면 직교라고 한다. 평면도에 그리는 방의 윤곽은 직교이면서 단조인 경우가 많아서, 방을 평면 위의 직교 단조 다각형으로 나타낸다.

직교 단조인 방의 윤곽에서 얻은 데이터 점 집합으로 다각형을 복원한다. 방 내부는 연결되어 있다. 윤곽을 이루는 각 변마다 데이터 점이 정확히 하나 있고, 그 점은 변의 내부에 놓인다. 각 데이터 점은 위치(x좌표와 y좌표)와 그 점이 놓인 변의 방향으로 이루어진다. 방향은 수평 변이면 H, 수직 변이면 V이다. 데이터 점 집합에서 복원되는 직교 단조 다각형의 경계 길이를 구하라.

그림 1. 평면 위의 데이터 점 12개: (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).

그림 1처럼 데이터 점 12개가 주어졌다고 하자. 각 데이터 점은 점과 함께, 그 점이 놓인 변의 방향을 나타내는 짧은 선분으로 그려져 있다. 이 데이터 점에서 그림 2와 같은 직교 단조 다각형을 복원할 수 있다. 이 데이터 점으로 복원되는 다각형은 그림 2 말고는 없다.

그림 2. 그림 1의 데이터 점에서 복원한 직교 단조 다각형.

그림 2의 다각형은 가장 왼쪽 수직 변에서 시작해 경계를 따라 시계 방향으로 길이가 2, 5, 2, 2, 5, 6, 4, 3, 5, 7, 4, 3인 변으로 이루어진다. 따라서 그림 1의 데이터 점 12개가 입력으로 주어지면 48을 출력해야 한다.

첫 줄에 데이터 점의 개수 $n$이 주어진다 ($4 \le n \le 500\,000$). 다음 $n$개 줄에 데이터 점이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 점의 x좌표와 y좌표, 그리고 방향을 나타내는 지시자 0 또는 1이 주어진다. 각 좌표는 $-2^{30}$ 이상 $2^{30}-1$ 이하인 정수이다. 지시자는 데이터 점이 놓인 변이 수평이면 0, 수직이면 1이다.

입력에서 복원한 직교 단조 다각형의 경계 길이를 출력한다. 입력에서 복원할 수 있는 직교 단조 다각형이 없으면 -1을 출력한다.