보호 천막

수빈이는 2차원 평면에서 농사를 짓는다. 모든 농작물은 x축 위, 즉 y좌표가 0인 곳에 심어져 있다. 내일은 농작물에 해로운 비가 내릴 예정이다. 비는 y축과 평행한 방향으로 곧게 내려오며, 모든 실수 x에 대해 (x, 0)을 향해 떨어진다.

수빈이는 농작물을 보호하기 위해 땅 위에 보호 천막을 설치했다. 보호 천막 하나는 x축과 평행한 선분으로 나타내며, 두께는 무시한다. 비가 천막 위에 떨어지면 빗물은 두 끝점 중 더 가까운 끝점으로 흘러간다. 두 끝점까지의 거리가 같다면 빗물은 양쪽 끝점으로 나뉘어 흐른다. 빗물이 끝점에 도착하면 그 점에서 다시 아래로 떨어진다. 두 천막이 같은 끝점을 공유하면 하나의 천막처럼 작동한다.

각 보호 천막은 (b_i, y_i)와 (e_i, y_i)를 잇는 선분으로 주어진다. 모든 b_i의 최솟값을 B, 모든 e_i의 최댓값을 E라고 하자. 수빈이의 농작물이 (B, 0)부터 (E, 0)까지의 구간에 심어져 있을 때, 이 구간의 모든 농작물을 보호하기 위해 새로 설치해야 하는 보호 천막 길이의 합의 최솟값을 구하라.

새로 설치하는 보호 천막도 x축과 평행해야 하며, y좌표는 양수여야 한다. 양 끝점의 좌표는 정수이고, 길이는 양수여야 한다.

첫째 줄에 이미 설치된 보호 천막의 개수 N이 주어진다. (1 ≤ N ≤ 25)

다음 N개의 줄에는 각 보호 천막의 정보 b_i, e_i, y_i가 주어진다. (0 ≤ b_i, e_i ≤ 10, 1 ≤ y_i ≤ 100,000)

보호 천막끼리는 겹치지 않는다. 단, 끝점만 겹치는 것은 가능하다.

모든 농작물을 보호하기 위해 새로 설치해야 하는 보호 천막 길이의 합의 최솟값을 출력한다.