Butterfly Effect

There are $n$ events about to happen. Each event ends with a positive outcome or a negative outcome, and that outcome changes the odds of the events that come later.

The events happen in the order given in the input. Event $i$ carries an integer base value $b_i$. To settle an event you roll a fair die whose faces are marked $1$ through $m$ and add the rolled number to the base value. If the sum is strictly greater than $0$, the outcome is positive. Otherwise the outcome is negative, and a sum of exactly $0$ counts as negative. If event $i$ ends positive, the base value of every later event $j$ becomes $b_j + p_{ij}$. If it ends negative, that base value becomes $b_j + q_{ij}$. All dice are rolled independently.

You have the power to intervene in an event. When you intervene, you roll two dice instead of one, look at both numbers, and keep the one you prefer. You decide whether to intervene immediately before that event's die is rolled, so you may use the outcomes of the earlier events to make the decision. You may intervene at most $k$ times. Compute the largest possible probability that event $n$ ends positive.

The first line contains three integers $n$, $k$, and $m$ separated by spaces ($1 \le k \le n \le 20$, $4 \le m \le 1000$): the number of events, the maximum number of interventions, and the number of faces on the die. The base values and the modifiers follow on $3n$ lines. Line numbers are counted from the first line of the input.

• Line $3i - 1$: the base value $b_i$ of event $i$, with absolute value at most $2000$.
• Line $3i$: $n - i$ integers $p_{i,i+1}, \dots, p_{i,n}$ separated by spaces, the amounts added to the base values of events $i + 1$ through $n$ when event $i$ ends positive.
• Line $3i + 1$: the values $q_{i,i+1}, \dots, q_{i,n}$ used when event $i$ ends negative, in the same format.

Every modifier has absolute value at most $2000$. The last event has no modifiers, so the final two lines of the input are empty.

Print on a single line the largest possible probability that the last event ends positive, rounded to six digits after the decimal point. Always print exactly six digits after the decimal point.