Problem Description

Snooky, the black cat, is playing a board game.

This board game uses a unique die. The die has a total of $ N $ faces, and each face has an equal probability of landing face up. The $ i $ -th face has an integer $ A_i $ written on it, and when this face lands up, the piece moves exactly $ A_i $ squares forward.

On the other hand, the squares used in this board game are not particularly unusual. There are a total of $ M $ squares arranged in a row, with the $ 1 $ -st square being the start and the $ M $ -th square being the goal. The $ i $ -th square has an integer $ B_i $ written on it, and if a piece lands on this square, it receives the following effects based on the value of $ B_i $ :

• If $ B_i $ is greater than or equal to $ 0 $ : The piece moves exactly $ B_i $ squares forward. However, the piece does not receive the effect of the square it moves to.
• If $ B_i $ is less than $ 0 $ : The piece is forced to rest for $ -B_i $ turns.

Now, what is the expected number of turns it takes for Snooky to reach the goal in this board game?

Note that if the piece attempts to move beyond the goal, it is considered to have reached the goal.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ B_1 $ $ B_2 $ $ ... $ $ B_M $

Output Format

Output the expected number of turns to reach the goal. The answer will be considered correct if the absolute or relative error is at most $ 10^{-4} $.

Sample Input and Output

Sample Input #1

3 4
1 2 3
0 1 -1 0

Sample Output #1

2.00000000000000000000

Sample Input #2

1 10
1
0 0 0 0 0 0 0 0 0 0

Sample Output #2

9.00000000000000177636

Sample Input #3

5 6
1 1 2 3 5
0 0 6 -10 1 0

Sample Output #3

4.47999999999999953815

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $2 \leq M \leq 10^5$
• $1 \leq A_i \leq M$
• $-10 \leq B_i \leq M$
• $ B_1 = B_M = 0 $

Sample Explanation 1

Considering the first turn for each die roll:
- If the die shows $ 1 $ : Move $ 1 $ square to the $ 2 $ -nd square. The effect of this square moves the piece to the $ 3 $ -rd square. In the next turn, any roll will reach the goal, so it takes a total of $ 2 $ turns to reach the goal.
- If the die shows $ 2 $ : Move $ 2 $ squares to the $ 3 $ -rd square. The effect of this square forces the piece to rest for $ 1 $ turn. The next turn is a rest turn, and in the turn after that, any roll will reach the goal, so it takes a total of $ 3 $ turns to reach the goal.
- If the die shows $ 3 $ : Move $ 3 $ squares to the $ 4 $ -th square, which is the goal, so it takes $ 1 $ turn to reach the goal.

Therefore, the expected value is $ 2/3 + 3/3 + 1/3 = 2 $.

见题面 Input 部分

见题面 Output 部分