1447번 - 보호 천막

수빈이는 2차원 세계에 살고있는 농부이다. 수빈이가 심은 농작물은 모두 x축 위(y 좌표가 0인 곳)에 심어져 있다. 내일은 수빈이의 농작물에 매우 해로운 비가 내린다고 한다. 비는 Y축에 평행한 방향으로 계속해서 내린다. 모든 x(정수가 아닐 수도 있다)에 대해서, 비는 (x, 0)을 향해서 떨어지게 된다.

수빈이는 농작물을 보호하기 위해 땅 위에 보호 천막을 설치했다. 보호 천막은 x축에 평행한 선분으로 나타낼 수 있으며, 두꼐는 무시할 수 있다. 비가 천막에 떨어졌을 때, 비는 양 끝 점중 가까운 점을 향해서 흘러간다. 비가 끝 점에 도착하면, 그 점부터 다시 아래로 내리게 된다. 만약, 비가 천막의 가운데에 떨어졌다면, 비는 양 끝점을 향해 나누어진 상태로 흐르게 된다. 두 천막이 끝점을 공유하는 경우에는 천막 하나와 같이 행동한다.

각각의 보호 천막은 (b_i, y_i), (e_i, y_i)를 잇는 선분으로 나타낼 수 있다. B를 b_i중에서 최솟값, E를 e_i중에서 최댓값이라고 하자. 수빈이의 농작물이 (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) 보호 천막이 겹쳐있는 경우는 없다. 단, 끝 점이 겹치는 경우는 있다.

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