The Neptune Adventure

Time limit1sMemory limit128 MB

Summary

Given a directed graph with travel times and a flood time per location, find the earliest safe arrival time from S to R, or report failure.

Level: Medium6 of 10
Topics: Shortest path, Graph, Greedy
Solved: No attempts yet

Problem

You are aboard the luxury liner Neptune, which is flooding fast. Find out whether you can escape the ship and reach the rescue team before you drown.

The ship's layout is described by a set of locations (cabins, lounges, and other rooms) and directed paths (hallways, elevators, Christmas trees, and stairs) between them, each with a travel time. You must find the shortest time it takes to get from your starting location to the rescue team.

A series of explosions floods the ship. Each location floods at a fixed time, and when a location floods, every path leading into or out of it floods as well. If you are inside a location, or on a path, at the very moment it floods, you drown. You may not travel through a location once it has flooded.

You win ties: if you reach a location that is not yet flooded at the exact moment the path you were traveling on floods, you survive; and if you reach the rescue team's location at the exact moment that location floods, you also survive.

Input

The first line contains a single integer $N$ ( $1 \le N \le 100$ ), the number of data sets. Each data set is given as follows.

The first line contains three integers $L$ , $S$ , and $R$ : $L$ ( $1 \le L \le 100$ ) is the number of locations, $S$ ( $1 \le S \le L$ ) is your starting location, and $R$ ( $1 \le R \le L$ ) is the rescue team's location.
The next $L$ $L$ lines describe the locations in order, starting with location $1$ $1$ . Line $i$ $i$ contains the integers $F\ T_1\ T_2\ \dots\ T_L$ $F T_{1} T_{2} \dots T_{L}$ :
- $F$ ( $0 \le F \le 10000$ ) is the time (in minutes, starting from time $0$ ) at which location $i$ floods. $F = 0$ means location $i$ never floods.
- $T_X$ ( $0 \le T_X \le 10000$ ) is the time in minutes to travel from location $i$ to location $X$ . $T_X = 0$ means there is no path from location $i$ to location $X$ . In particular, the self entry $T_i$ is $0$ .

Paths are directed: the time from location $i$ to location $X$ need not equal the time from location $X$ to location $i$ , and some paths exist in only one direction.

Output

For each data set, print a single line with the shortest time in minutes it takes to reach the rescue team from your starting location without drowning. If it is impossible to reach the rescue team, print GENE HACKMAN instead.

Examples3

Example 1

Input

Expected output

2
GENE HACKMAN

Example 2
Input
```
1
2 1 2
0 0 5
0 0 0
```
Expected output
```
5
```
Example 3
Input
```
1
2 1 2
0 0 3
3 0 0
```
Expected output
```
3
```