고지대 산행

헬렌은 친구들과 고지대를 걷고 있다. 야영지 A에서 전망대 B까지 걸어가는 것이 이번 일정이다.

헬렌이 고산병으로 어지러움을 느끼기 시작했다. 지나는 지점의 고도 중 가장 높은 값이 최대한 낮은 경로를 찾아 주자.

지형은 삼각형 여러 개로 주어진다. 경로는 A에서 B까지 이어지는 꺾은선이고, 경로를 이루는 각 선분은 삼각형 하나에 완전히 들어가야 한다. 즉 경로는 지형 표면을 벗어나지 않는다. 경로의 최고 고도는 그 경로 위에 있는 점의 $z$ 좌표 중 가장 큰 값이다. A에서 B까지 가는 모든 경로 가운데 최고 고도의 최솟값을 구하라.

지형은 $10^6 \times 10^6$ 크기의 정사각형 영역을 덮는다.

첫 줄에 지형을 이루는 삼각형의 개수 $n$이 주어진다 ($2 \le n \le 2000$).

다음 $n$개의 줄에는 삼각형 하나의 좌표를 나타내는 정수 아홉 개 $x_{i1}$, $y_{i1}$, $z_{i1}$, $x_{i2}$, $y_{i2}$, $z_{i2}$, $x_{i3}$, $y_{i3}$, $z_{i3}$이 주어진다. 모든 좌표는 닫힌구간 $[0, 10^6]$에 속한다.

마지막 두 줄에는 각각 정수 세 개가 주어진다. 야영지 A의 좌표 $x_A$, $y_A$, $z_A$와 전망대 B의 좌표 $x_B$, $y_B$, $z_B$이다.

주어진 삼각형은 끊긴 곳 없이 이어진 지형 하나를 이룬다. 삼각형을 XY 평면에 정사영한 도형은 모두 넓이가 0이 아니며, 서로 겹치지 않으면서 정사각형을 빈틈없이 채운다. 한 삼각형의 꼭짓점이 다른 삼각형의 변 내부에 놓이는 일은 없다. A와 B는 지형 표면 위에 있는 서로 다른 점이다.

A에서 B까지 가는 경로의 최고 고도가 가질 수 있는 가장 작은 값을 정수 하나로 출력한다.