問題文
黑猫斯努克正在和双六玩耍。
这个双六使用了不寻常的骰子。 这个骰子已经全部 有 N 张面孔,每张面孔出现的概率相同。 第 i 面是一个整数。 写着 A_i ,当这一面出现时,将棋子准确移动。 A_i 前进。
另一方面,这个双六中使用的方块并不是那么不寻常。 总共 M 方块排成一排,1 第格开始,M 第一个方格是目标。 i 是一个整数 如果写入 B_i 并且停在这个方块上, B_i 的值具有以下效果。
- B_i 是 0 或更多:精确移动棋子 B_i 前进。但前进的空间效果不会受到影响。 如果小于
- B_i 是 0 :-B_i 关闭。
现在,Snuke 使用双六到达目标需要多少回合?
此外,在这个双六中,如果你试图超越目标,它也会被视为一个目标。
制約
- 1≦N≦10^5
- 2≦M≦10^5
- 1≦A_i≦M
- -10≦B_i≦M
- B_1=B_M=0
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 ... A_N B_1 B_2 ... B_M
出力
输出到达目标所需的预计圈数。 然而,如果绝对或相对误差 10^{-4} 如果答案如下,则视为正确。
入力例 1
3 4 1 2 3 0 1 -1 0
出力例 1
2.00000000000000000000
考虑到第一回合的每次掷骰,如下所示。
- 突出的眼睛 对于 1 :1 前进, 它停在第2 个方格。由于该质量的影响, 前往第3 个方格。在下一个回合,无论你掷什么,你都可以得分,所以总数将为 2 需要转弯。
- 突出的眼睛 对于 2 :2 前进, 它停在第3 个方格。由于该质量的影响, 前往第1 关闭。下个回合是假期,下个回合无论你掷什么都可以得分,所以目标总共包括 它停在第 3 需要转弯。
- 突出的眼睛 对于 3 :3 前进, 它停在第4 个方格。也就是说,1 你可以在一个回合内达到目标。
因此,期望值为 2/3 + 3/3 + 1/3 = 2 变为。
入力例 2
1 10 1 0 0 0 0 0 0 0 0 0 0
出力例 2
9.00000000000000177636
入力例 3
5 6 1 1 2 3 5 0 0 6 -10 1 0
出力例 3
4.47999999999999953815