J. Spectacular Ending
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The game "Dungeons and Rainbows" uses dices of various shapes and various number of faces. The game process consists of moving between dungeons and performing various actions. The game has $$$n$$$ states in total, that number already includes all possible combinations of positions, items, skills and so on. The game rules define for each state which particular dice should be used in order to determine the next state. As the dice being used can have more than $$$n$$$ faces, rules of the game define how many faces of the dice should correspond to each particular outcome (transition to some other state).

For example, consider there are $$$3$$$ states in a game and for one of them it is required to use a dice with $$$5$$$ faces. One possible distribution can be the following: $$$2$$$ faces correspond to transition to the state $$$1$$$, $$$1$$$ face corresponds to transition to state $$$2$$$ and remaining $$$2$$$ faces correspond to transition to state $$$3$$$.

Players start the game in state $$$1$$$ and the game lasts $$$k$$$ rounds. In order to get a spectacular ending of the game players must make a transition to state $$$s$$$ in the last round. Note, that it doesn't matter whether they have already visited this state in other rounds or not.

Experienced host knows probabilities of each face of every dice. In each round he chooses which faces will correspond to which outcomes. So, at the beginning of every round the host assigns the next state for face of the dice that will be used in this round (this is determined by current state only). If it happens that players transit to the same state more than once, the host can make a different assignment of outcomes to faces every time.

The host wants to maximize the probability that the game will have a spectacular ending. Calculate this probability if the host acts optimal.

Input

The first line contains the number of states $$$n$$$ ($$$2 \le n \le 1000$$$), the number of rounds in the game $$$k$$$ ($$$1 \le k \le 100$$$) and the index of the state needed for spectacular ending $$$s$$$ ($$$1 \le s \le n$$$).

Next $$$n$$$ lines contain transition rules for each of the states. The first $$$n$$$ numbers of the $$$i$$$-th row determine the number of dice faces $$$F_{ij}$$$ ($$$0 \le F_{ij} \le 1000$$$) which correspond to transitions to each of $$$n$$$ states from the $$$i$$$-th state. The total number of dice faces satisfies $$$2 \le \sum_j F_{ij}\le 1000$$$. Than follows the denominator $$$Q_i$$$ ($$$\sum_j F_{ij} \le Q_i\le 10^6$$$) of probabilities of all dice faces. And further along $$$\sum_j F_{ij}$$$ numerators $$$P_{ij}$$$ ($$$1 \le P_{ij} \le Q_i$$$) of probabilities of all dice faces. The sum of probabilities of all faces equals to $$$1$$$.

Output

Print maximum probability to get the spectacular ending if the host acts in an optimal way with absolute error less than $$$10^{-9}$$$.

Examples
Input
2 1 2
1 1 3 1 2
1 1 3 2 1
Output
0.666666666667
Input
3 3 3
1 1 0 3 2 1
0 1 1 3 2 1
1 0 1 3 2 1
Output
0.592592592593
Input
2 2 2
2 1 4 1 2 1
2 1 4 1 1 2
Output
0.5