Expected Steps to Reach the Dream in n‐Dimensional Space

In an n-dimensional space there is a dream located at \( (d_1, d_2, \ldots, d_n) \). You start at the origin \( (0,0,\ldots,0) \) and take steps of unit length. However, you do not know in which direction the dream lies. At each step you uniformly at random choose one of the n positive coordinate directions and move one unit in that direction. In addition, during each step there is a probability \( p=\sum_{i=1}^k p_i \) that you get distracted and your journey resets. When a reset occurs, you restart from one of k given restart locations \( (a_{i,1},a_{i,2},\ldots,a_{i,n}) \) with probability \( p_i \) (\(i=1,2,\ldots,k\)).

Your task is to compute the expected number of steps required to finally reach the dream, where reaching the dream means that in each dimension the coordinate is at least \( d_i \) (i.e. you have reached or exceeded \( d_i \) in every coordinate).

Note on Modeling: It is often easier to transform the state by letting \( y_i=\max(0,d_i-x_i) \). Then the initial state becomes \( (d_1,d_2,\ldots,d_n) \) and the terminal state is \( (0,0,\ldots,0) \). A step in the \( i\)th direction decreases \( y_i \) by one unit (if \( y_i>0 \); otherwise it remains 0). The resets take you to a new state \( y' \) where for each \( i\), \( y'_i=\max(0,d_i-a_{j,i}) \) if the chosen restart location is \( (a_{j,1},\ldots,a_{j,n}) \).

Let \( F(y) \) denote the expected remaining steps from state \( y=(y_1,y_2,\ldots,y_n) \). For any nonterminal state (i.e. \( y\neq (0,0,\ldots,0) \)) the recurrence is:

[ F(y)=1+\frac{1-p}{n}\sum_{i=1}^n F(y^{(i)})+p\cdot A, ]

where \( y^{(i)} \) is the state obtained by decrementing the \( i\)th coordinate by 1 (if it is positive; otherwise it stays 0) and \( A \) is a constant representing the expected steps after a reset. Writing \( F(y)=f(y)+A \) leads to a recurrence for the function \( f(y) \):

[ \begin{cases} f(y)=1+\frac{1-p}{n}\sum_{i=1}^n f(y^{(i)}) & \text{for } y\neq (0,0,\ldots,0),\[1mm] f(0,0,\ldots,0)=-A. \end{cases} ]

For each restart state \( (a_{j,1},\ldots,a_{j,n}) \) the corresponding transformed state is \( R_j=(\max(0,d_1-a_{j,1}),\ldots,\max(0,d_n-a_{j,n})) \). The constant \( A \) is then determined by the condition

[ \sum_{j=1}^k \frac{p_j}{p}, (f(R_j)-A,g(R_j))=0, ]

In our solution the functions are computed over the finite state space \( y_i\in [0,d_i] \). Finally, the answer is given by
\( F(\text{initial})=f(\text{initial})+A \), where the initial state is \( (d_1,d_2,\ldots,d_n) \).

You are to output the expected steps as a floating–point number (output with at least 6 decimal places of precision).

inputFormat

The input begins with two integers \( n \) and \( k \) on a line, where \( n \) is the number of dimensions and \( k \) is the number of restart locations.

The next line contains \( n \) positive integers: \( d_1,d_2,\ldots,d_n \) which represent the dream location (the thresholds in each dimension).

The following line contains \( k \) real numbers: \( p_1,p_2,\ldots,p_k \) (each between 0 and 1) such that \( p=\sum_{i=1}^k p_i \) is the total reset probability.

Each of the next \( k \) lines contains \( n \) nonnegative integers. The \( i\)th such line gives \( a_{i,1},a_{i,2},\ldots,a_{i,n} \), the coordinates of the \( i\)th restart location.

outputFormat

Output a single real number — the expected number of steps needed to reach the dream. The answer should be printed with at least 6 digits after the decimal point.

sample

1 1
3
0.5
0

14.000000