“Dungeons and Rainbows” 游戏使用各种形状和面数的骰子。游戏过程包括在地下城之间移动并执行各种动作。游戏总共有 $n$ 个状态，这个数字已经包含了位置、物品、技能等所有可能的组合。游戏规则为每个状态定义了应该使用哪种特定的骰子来确定下一个状态。由于所使用的骰子面数可能多于 $n$，游戏规则定义了骰子的多少个面应对应于每个特定的结果（即转移到其他某个状态）。

例如，考虑一个游戏有 3 个状态，其中一个状态需要使用一个 5 面的骰子。一种可能的分布如下：2 个面对应转移到状态 1，1 个面对应转移到状态 2，其余 2 个面对应转移到状态 3。

玩家从状态 1 开始游戏，游戏持续 $k$ 轮。为了获得游戏的“壮观结局”，玩家必须在最后一轮转移到状态 $s$。注意，玩家是否在其他轮次中访问过该状态并不重要。

经验丰富的游戏主持者知道每个骰子每一面的概率。在每一轮中，他可以选择哪些面对应哪些结果。因此，在每一轮开始时，主持者为该轮将要使用的骰子的每一个面分配下一个状态（这仅由当前状态决定）。如果玩家多次转移到同一个状态，主持者每次都可以对面的结果进行不同的分配。

主持者希望最大化游戏获得“壮观结局”的概率。如果主持者采取最优策略，请计算该概率。

输入格式

第一行包含状态数 $n$ ($2 \le n \le 1000$)，游戏轮数 $k$ ($1 \le k \le 100$) 以及获得“壮观结局”所需的状态索引 $s$ ($1 \le s \le n$)。

接下来的 $n$ 行包含每个状态的转移规则。第 $i$ 行的前 $n$ 个数字确定了从第 $i$ 个状态转移到每个状态的骰子面数 $F_{ij}$ ($0 \le F_{ij} \le 1000$)。骰子面总数满足 $2 \le \sum_j F_{ij} \le 1000$。随后是所有骰子面概率的分母 $Q_i$ ($\sum_j F_{ij} \le Q_i \le 10^6$)。再往后是所有骰子面概率的分子 $P_{ij}$ ($1 \le P_{ij} \le Q_i$)。所有面的概率之和等于 1。

输出格式

输出如果主持者采取最优策略，获得“壮观结局”的最大概率，要求绝对误差小于 $10^{-9}$。

样例

样例输入 1

2 1 2
1 1 3 1 2
1 1 3 2 1

样例输出 1

0.666666666667

样例输入 2

3 3 3
1 1 0 3 2 1
0 1 1 3 2 1
1 0 1 3 2 1

样例输出 2

0.592592592593

样例输入 3

2 2 2
2 1 4 1 2 1
2 1 4 1 1 2

样例输出 3

0.5