Problem B
Maximizing (And Minimizing) Your Winnings

You are a contestant on a game show where the goal is to win as much money as you can. The game is played in a building with many numbered rooms, and starting from room 1 with no money, you take a fixed number of turns. For each turn you either stay in the same room, or walk to an adjacent room. Then you do this again, and again, etc. Each turn earns you some amount of money (or perhaps none). All rooms are connected, but going through a door in one direction may earn a different amount of money than going through in the other direction.

Input

Input consists of up to $50$ games. Each game’s description starts with an integer $1 \le n \le 50$, indicating that rooms $1, 2, \ldots , n$ are in use. This is followed by $n$ lines that describe an $n\times n$ matrix of numbers in the range $[0,2\, 000]$. The matrix entry for row $i$ and column $j$ indicates the amount of money received by going directly from room $i$ to room $j$ (or for staying in the same room if $i = j$) on any turn. Following the description of the rooms is an integer $0 \le m \le 5\, 000$, indicating the number of turns that you take. Input ends when $n$ is zero.

Output

For each game, print the maximum and minimum dollar amounts you can win. Each amount is less than $2^{31}-1$.

3
2 17 11
7 1 8
11 18 19
1
4
2 0 0 0
0 2 0 0
0 0 2 20
0 0 0 2
5
0

17 2
42 0