Butterfly Effect#8182

Butterfly Effect

1 second

256 megabytes

Easy

A sequence of events is given, occurring one after another. Each event may result in either a positive or a negative outcome and influences the probabilities of outcomes of subsequent events.

The events occur in the order specified in the input. For each event $i$ , an integer base value $b_{i}$ b_i is given. To determine the outcome of an event, a fair $m$ -sided die is rolled, with faces numbered from $1$ to $m$ , and the result is added to the base value. If the resulting sum is strictly positive, the outcome is considered positive; otherwise (including when the result is zero), the outcome is considered negative.

If event $i$ results in a positive outcome, the base values of all subsequent events are modified according to a set of modifiers: for each $j > i$ j > i, the new value becomes $b_{j} + p_{ij}$ b_j + p_{ij}, where $p_{ij}$ p_{ij} is the modifier for event $j$ . If the outcome is negative, a different set of modifiers is used: the new value becomes $b_{j} + q_{ij}$ b_j + q_{ij}, where $q_{ij}$ q_{ij} is the corresponding modifier.

You are allowed to intervene in at most $k$ events. When you intervene, instead of rolling one die, you roll two dice and may choose either of the two results. For each event, the decision to intervene is made immediately before the roll, taking into account the outcomes of all previous events.

Your task is to maximize the probability that the final event has a positive outcome.

Input

The first line contains three integers $n, k$ and $m (1 \leq k \leq n \leq 20, 4 \leq m \leq 1000)$ m~(1 \le k \le n \le 20, 4 \le m \le 1000) — the number of events, the maximum number of allowed interventions, and the number of sides on the die.

The following $3 n$ lines describe the events:

Line $3 i - 2$ 3i - 2: one integer $b_{i}$ b_i — the base value of event $i (∣ b_{i} ∣ \leq 2000)$ i~(|b_i| \le 2000).
Line $3 i - 1$ 3i - 1: $n - i$ n - i integers $p_{i, i + 1}, \dots, p_{i, n}$ p_{i,i+1}, \dots, p_{i,n} — the modifiers for subsequent events if event $i$ has a positive outcome $(∣ p_{ij} ∣ \leq 2000)$ (|p_{ij}| \le 2000).
Line $3 i$ : $n - i$ n - i integers $q_{i, i + 1}, \dots, q_{i, n}$ q_{i,i+1}, \dots, q_{i,n} — the modifiers for subsequent events if event $i$ has a negative outcome $(∣ q_{ij} ∣ \leq 2000)$ (|q_{ij}| \le 2000).

For the last event, there are no modifiers, so the corresponding two lines are empty.

Output

Print one number — the maximum probability that the final event has a positive outcome. The answer must be printed with precision up to $6$ digits after the decimal point.

Examples

Example 1

Example 2