CF553E.Kyoya and Train

Kyoya Ootori wants to take the train to get to school. There are n train stations and m one-way train lines going between various stations. Kyoya is currently at train station 1, and the school is at station n. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after t time units, he will have to pay a fine of x.

Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line i has ticket cost c__i, and a probability distribution p__i, k which denotes the probability that this train will take k time units for all 1 ≤ k ≤ t. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).

Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

京谷大鸟想要乘坐火车去学校。一共有 $n$ 个火车站和 $m$ 条单向火车线路，连接着不同的车站。京谷当前位于 1 号车站，而学校位于 $n$ 号车站。乘坐火车需要购买车票（需支付费用），且火车到达目的地也需要一定的时间。然而，火车运行并不完美，其到达目的地所需的时间是随机的。如果京谷在严格超过 $t$ 个时间单位之后才到达学校，他将被处以 $x$ 的罚款。

每条火车线路由一张车票价格以及一个关于运行时间的概率分布来描述。更准确地说，第 $i$ 条火车线路的车票费用为 $c_i$，其运行时间的概率分布为 $p_{i,k}$，表示该列车恰好耗时 $k$ 个时间单位的概率（对所有满足 $1 \le k \le t$ 的 $k$）。京谷所乘坐的各列火车的运行时间是相互独立的随机变量（此外，若京谷多次乘坐同一列火车，每次的运行时间也可能不同，且彼此独立）。

京谷希望以最小的期望总花费（车票费用加上可能产生的迟到罚款）抵达学校。当然，京谷拥有一个最优的出行计划；并且每当他抵达一个车站时，都可以根据剩余可用时间重新计算后续最优策略。若京谷始终采取最优行动，那么他抵达学校所需支付的期望总费用是多少？

The first line of input contains four integers n, m, t, x (2  ≤  n  ≤ 50, 1 ≤ m ≤ 100, 1 ≤ t ≤ 20 000, 0 ≤ x ≤ 106).

The next 2_m_ lines contain the description of the trains.

The 2_i_-th line will have 3 integers a__i, b__i, c__i, representing a one way train from station a__i to b__i with ticket cost c__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 0 ≤ c__i ≤ 106). There will always be at least one path from any station to the school.

The (2_i_ + 1)-th line will contain t integers, p__i, 1, p__i, 2, ..., p__i, t where p__i, k / 100000 is the probability that this train will take k units of time to traverse (0 ≤ p__i, k ≤ 100 000 for 1 ≤ k ≤ t, ).

It is guaranteed that there is no more than one train between each pair of platforms in each of the directions.

输入的第一行包含四个整数 $n$、$m$、$t$、$x$（满足 $2 \le n \le 50$，$1 \le m \le 100$，$1 \le t \le 20\,000$，$0 \le x \le 10^6$）。

接下来的 $2m$ 行描述了所有列车的信息。

第 $2i$ 行包含三个整数 $a_i$、$b_i$、$c_i$，表示一条从车站 $a_i$ 到车站 $b_i$ 的单向列车，车票费用为 $c_i$（其中 $1 \le a_i, b_i \le n$，$a_i \ne b_i$，$0 \le c_i \le 10^6$）。任意车站到学校之间始终至少存在一条路径。

第 $(2i + 1)$ 行包含 $t$ 个整数 $p_{i,1},\, p_{i,2},\, \dots,\, p_{i,t}$，其中 $p_{i,k} / 100000$ 表示该列车通过所需时间为 $k$ 个单位时间的概率（对 $1 \le k \le t$，有 $0 \le p_{i,k} \le 100\,000$，且 ）。

保证在每一对站点之间的每个方向上至多只有一列列车。

Print a single real number that is equal to an optimal expected cost of getting to school. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

输出一个实数，表示到达学校的最优期望成本。若答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。

The optimal strategy in the first case is as follows:

First, travel along first train line. With probability 1 / 2 Kyoya will take 1 time unit. Otherwise, Kyoya will take 3 time units.

If the train takes 1 time unit, travel along the 4th train line. Kyoya will make it to school in time with probability 1 / 2. Otherwise, if the train takes 3 time units, travel along the 2nd train line. Kyoya will make it to school in time with probability 1 / 10.

Since the cost of all train lines are zero, we can just look at the probability that Kyoya will incur the penalty. The probability that Kyoya will have to pay the penalty is 1 / 2 × 1 / 2 + 1 / 2 × 9 / 10 = 7 / 10. We can show that no other strategy is strictly better.

The optimal strategy in the second case is to travel along 1 → 2 → 4 no matter what. Kyoya will incur the penalty with probability 3 / 4, and the cost of the trains is 200, thus the expected cost is 200.75.

第一种情况下的最优策略如下：

首先，沿第一条列车线路行驶。以 $1/2$ 的概率，京也花费 $1$ 个时间单位；否则，他将花费 $3$ 个时间单位。

若列车耗时 $1$ 个时间单位，则沿第四条列车线路行驶。此时京也准时到达学校的概率为 $1/2$。否则，若列车耗时 $3$ 个时间单位，则沿第二条列车线路行驶。此时京也准时到达学校的概率为 $1/10$。

由于所有列车线路的费用均为零，我们只需考察京也需支付罚金的概率。京也需支付罚金的概率为

$$\frac{1}{2} \times \frac{1}{2} + \frac{1}{2} \times \frac{9}{10} = \frac{7}{10}.$$

可以证明，不存在严格更优的其他策略。

第二种情况下的最优策略是无论发生何种情况，均沿 $1 \to 2 \to 4$ 行驶。京也需支付罚金的概率为 $3/4$，而列车费用为 $200$，因此期望总成本为 $200.75$。