Get Them All

To make sure the contestants can easily reach the regional contest site, the organizers have prepared several robot-driven vehicles. The vehicles visit $n$ predetermined junctions and carry the contestants waiting there to the contest. A computer-controlled Transportation Center (TC) decides the number of seats of each vehicle and the time at which each vehicle first leaves the contest site.

Whenever a new vehicle is needed, a request is sent to the TC. As long as the seat count stays above 3, each new vehicle has fewer seats than the previous one: the $i$-th vehicle has $\max(s - (i-1)\cdot t,\ 3)$ seats ($i = 1, 2, 3, \dots$). The first vehicle leaves the contest site exactly at 8:00am (time $0$). When the TC receives a request for a new vehicle, it prepares one, and exactly $2$ seconds after receiving the request that vehicle leaves the contest site. If several requests arrive at the same time, only one of them is honored.

At junction $j$ each vehicle performs the tasks below. If more than one vehicle is at $j$ at the same time, they perform the tasks in order of their service time: the vehicle with the longest service time goes first. A vehicle's service time is the current time minus the time at which that vehicle first left the contest site (junction $0$).

1. If $j = 0$ (the contest site), every contestant in the vehicle gets off. Otherwise the vehicle picks up as many contestants as it can (until the vehicle is full or no contestant is left at junction $j$).

2. If, after that, any contestant is still left at junction $j$ ($j > 0$), the vehicle sends a request for a new vehicle to the TC.

3. Finally the vehicle starts moving toward the next junction $k$, which the robot-driver chooses as follows (this also applies at junction $0$):

   • If the vehicle is full, $k = 0$.
   • Otherwise, if no other vehicle has left junction $j$ yet, $k = (j+1) \bmod n$.
   • Otherwise, $k = (k_0+1) \bmod n$ if that value is different from $j$.
   • Otherwise, $k = (k_0+2) \bmod n$.
   • (Here $k_0$ is the "next junction" chosen by the most recent vehicle to leave junction $j$.)

The three tasks above happen instantly (in $0$ seconds). The time needed to travel from each junction to every other junction is given. All contestants have reached a suitable junction by 8:00am and do not leave until some vehicle picks them up. Given the number of contestants waiting at each junction and a time limit, determine the time at which everyone reaches the contest, or how many contestants have reached the contest by the time limit.

The input consists of several datasets. Each dataset has the following form:

• A line with the name of the set (2 to 20 alphanumeric characters).
• A line with three positive integers $n$, $s$, and $t$ ($2 < n < 11$).
• Then $n$ lines, each with $n-1$ integers. The $i$-th line ($i = 1, 2, 3, \dots$) gives the time (in seconds) needed to travel from junction $i-1$ to every other junction (all except $i-1$), listed in order of destination index $0, 1, 2, \dots, n-1$.
• Then $n-1$ lines, each with one non-negative integer. The $i$-th line ($i = 1, 2, 3, \dots$) is the number of contestants waiting at junction $i$.
• The last line of the dataset is the time limit (in seconds, less than $10000000$).

Integers on the same line are separated by exactly one space. The total number of contestants is at most $1000$.

The end of the input is marked by a line containing only TheEnd.

For each set, print two lines. The first line is the name of the set exactly as it appears in the input. On the second line, if the time needed to bring all contestants to the contest does not exceed the given time limit, print that time (in seconds) as <time> seconds needed. Otherwise, print the number of contestants that reached the contest by the time limit as <count> contestants reached.