넵튠호 탈출

당신은 빠르게 침수되고 있는 호화 여객선 넵튠호에 타고 있습니다. 물에 빠지기 전에 배를 탈출해 구조대에게 도달할 수 있는지 판단하세요.

배의 구조는 여러 위치(객실, 라운지 등 여러 방)와 그 위치들을 잇는 방향성 통로(복도, 엘리베이터, 크리스마스트리, 계단 등)로 표현되며, 각 통로에는 이동 시간이 정해져 있습니다. 출발 위치에서 구조대가 있는 위치까지 가는 데 걸리는 최소 시간을 구해야 합니다.

배 곳곳에서 폭발이 일어나 침수가 진행됩니다. 각 위치는 정해진 시각에 침수되며, 어떤 위치가 침수되면 그 위치로 드나드는 모든 통로도 함께 침수됩니다. 침수되는 바로 그 순간에 그 위치 안에 있거나 그 통로 위에 있으면 물에 빠져 죽습니다. 이미 침수된 위치는 지나갈 수 없습니다.

동점(타이)일 때는 당신이 이깁니다. 지나오던 통로가 침수되는 바로 그 순간에 아직 침수되지 않은 위치에 도착하면 살아남고, 구조대가 있는 위치가 침수되는 바로 그 순간에 그 위치에 도착해도 살아남습니다.

첫 줄에는 데이터 집합의 개수 $N$ ($1 \le N \le 100$)이 주어집니다. 각 데이터 집합은 다음과 같이 주어집니다.

• 첫 줄에는 세 정수 $L$, $S$, $R$이 주어집니다. $L$ ($1 \le L \le 100$)은 위치의 개수, $S$ ($1 \le S \le L$)는 출발 위치, $R$ ($1 \le R \le L$)은 구조대의 위치입니다.
• 이어지는 $L$개의 줄은 위치 $1$번부터 순서대로 각 위치의 정보를 담고 있습니다. $i$번째 줄에는 정수 $F\ T_1\ T_2\ \dots\ T_L$이 주어집니다.
  • $F$ ($0 \le F \le 10000$)는 위치 $i$가 침수되는 시각(분 단위, 시각 $0$부터 시작)입니다. $F = 0$이면 위치 $i$는 절대 침수되지 않습니다.
  • $T_X$ ($0 \le T_X \le 10000$)는 위치 $i$에서 위치 $X$로 이동하는 데 걸리는 시간(분)입니다. $T_X = 0$이면 위치 $i$에서 위치 $X$로 가는 통로가 존재하지 않음을 뜻합니다. 특히 자기 자신에 해당하는 값 $T_i$는 $0$입니다.

통로에는 방향이 있습니다. 위치 $i$에서 위치 $X$로 가는 시간과 위치 $X$에서 위치 $i$로 가는 시간은 다를 수 있으며, 어떤 통로는 한 방향으로만 존재합니다.

각 데이터 집합마다, 출발 위치에서 물에 빠지지 않고 구조대에게 도달하는 데 걸리는 최소 시간(분)을 한 줄에 출력하세요. 구조대에게 도달하는 것이 불가능하면 대신 GENE HACKMAN을 출력하세요.