케난은 바쿠의 대로를 따라 빌딩과 구름다리(스카이워크)의 설계도를 그렸다.

0번부터 n - 1번까지 번호가 붙은 n개의 빌딩과 0번부터 m - 1번까지 번호가 붙은 m개의 구름다리가 있다.

설계도는 2차원 평면에 그려져 있고 빌딩은 수직선분, 구름다리는 수평선분이다.

빌딩 i (0 ≤ i ≤ n - 1)의 바닥은 점 (x_i, 0)에 위치하고, 빌딩의 높이는 h_i이다.

따라서 이 빌딩은 점 (x_i, 0)과 점 (x_i, h_i)를 잇는 선분이다.

구름다리 j (0 ≤ j ≤ m - 1)는 빌딩 l_j와 빌딩 r_j에 끝점을 둔 선분이며 y-좌표는 양수 y_j이다.

따라서 이 구름다리는 점 (x_ij, y_j)와 점 (x_rj, y_j)를 잇는 선분이다.

구름다리와 빌딩이 공통된 점을 공유하는 경우 교차한다라고 한다.

따라서 하나의 구름다리는 양 끝점에서 두 빌딩과 교차하고, 중간에 다른 빌딩들과 교차할 수도 있다.

케난은 빌딩과 구름다리만 걸어서 빌딩 s의 바닥에서 빌딩 g의 바닥까지 도달하는 최단경로의 길이를 구하고 싶다.

만약 그런 경로가 존재하지 않는다면 존재하지 않음을 판단하고 싶다.

땅 위로 걷는 것, 즉 x-좌표가 0인 수평선을 따라 걷는 것은 허락되지 않는다.

교차한 점에서는 구름다리에서 빌딩으로 넘어갈 수도 있고 빌딩에서 구름다리로 넘어갈 수도 있다. 만약 두 구름다리의 끝점이 동일한 점이라면, 한 구름다리에서 다른 구름다리로 넘어갈 수 있다.

당신은 케난이 질문에 답할 수 있도록 도우면 된다.

Sky Walking timer 4초 memory 1024MB

Sky Walking 4초 1024MB