Expected Rounds in the Window Pattern Cutting Competition

In this problem, two contestants, Xiao Cai and Xiao Xi, are cutting "window patterns" (剪窗花) with beauty levels from \(1\) to \(n\). Their respective skills are given by arrays \(a_{1..n}\) and \(b_{1..n}\) such that the probability of producing a window pattern with beauty \(k\) is

\[ P(\text{beauty}=k) = \frac{a_k}{\sum_{i=1}^n a_i} \quad \text{for Xiao Cai}, \qquad P(\text{beauty}=k) = \frac{b_k}{\sum_{i=1}^n b_i} \quad \text{for Xiao Xi}. \]

The competition proceeds in rounds. In each round, both contestants independently produce a window pattern. The outcomes are:

• If Xiao Cai's beauty is greater than Xiao Xi's, then Xiao Cai wins the round.
• If it is smaller, he loses the round.
• If they are equal, the round is a draw.

Xiao Cai maintains a counter that starts at \(0\). It is updated each round as follows:

• Win: counter increases by \(+1\).
• Loss: counter decreases by \(-1\); however, since the counter does not allow negative values, if after decrement the value is \(\le 0\) the counter is reset to \(0\).
• Draw: counter remains unchanged.

The match ends immediately once the counter reaches exactly \(m\). Given the arrays \(a\) and \(b\) and the threshold \(m\), compute the expected number of rounds until the competition ends.

Note: Let \[ \begin{aligned} p_{win} &= \frac{\sum_{i=2}^n \sum_{j=1}^{i-1}a_i b_j}{\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)},\\ p_{draw} &= \frac{\sum_{i=1}^n a_i b_i}{\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)},\\ p_{loss} &= 1-p_{win}-p_{draw}. \end{aligned} \] The state of the counter is \(x\) (with \(0 \le x < m\)). The expected additional rounds \(E(x)\) satisfies:

• For \(x=0\): \[ (1-p_{loss}-p_{draw})E(0) - p_{win}E(1)= 1. \]
• For \(x=1\): \[ -p_{loss}E(0)+(1-p_{draw})E(1)-p_{win}E(2)= 1. \]
• For \(2\le x\le m-2\): \[ -p_{loss}E(x-1)+(1-p_{draw})E(x)-p_{win}E(x+1)= 1. \]
• For \(x = m-1\): \[ -p_{loss}E(m-2)+(1-p_{draw})E(m-1)= 1, \quad \text{(since a win brings the counter to } m \text{ and } E(m)=0\text{)}. \]

Your task is to compute \(E(0)\), the expected number of rounds starting from counter value \(0\). It is guaranteed that \(p_{win}+p_{loss}+p_{draw}=1\) and that \(p_{win} = 1-p_{loss}-p_{draw}\).

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \le n \le \text{some limit},\; 1 \le m \le \text{some limit}) \), representing the maximum beauty level and the threshold for the counter, respectively.

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) representing Xiao Cai's skill levels.

The third line contains \(n\) positive integers \(b_1, b_2, \dots, b_n\) representing Xiao Xi's skill levels.

outputFormat

Output a single real number, the expected number of rounds until the contest ends. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

3 2
1 1 1
1 1 1

9.000000