AT_jag2017summer_day1_c すごろく

[problemUrl]: https://atcoder.jp/contests/jag2017summer-day1/tasks/jag2017summer_day1_c 黒猫のスヌケ君はすごろくで遊んでいます。 このすごろくでは変わったサイコロを使っています。 このサイコロには全部で $ N $ 個の面があり、それぞれの面が出る確率は全て同じです。 $ i $ 番目の面には整数 $ A_i $ が書かれていて、この面が出たときは駒をちょうど $ A_i $ マス進めます。 一方、このすごろくで使っているマスはそれほど変わったものではありません。 全部で $ M $ 個のマスが一列に並んでいて、$ 1 $ 番目のマスがスタート、$ M $ 番目のマスがゴールです。 $ i $ 番目のマスには整数 $ B_i $ が書かれていて、このマスに止まった場合は $ B_i $ の値によって以下のような効果を受けます。 - $ B_i $ が $ 0 $ 以上である場合：駒をちょうど $ B_i $ マス進める。ただし、進めた先のマスの効果は受けない。 - $ B_i $ が $ 0 $ 未満である場合：$ -B_i $ ターン休みとなる。 さて、スヌケ君がこのすごろくでゴールするまでにかかるターン数の期待値はいくらでしょうか？ なお、このすごろくではゴールを越えて進もうとした場合もゴールとみなされます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ B_1 $ $ B_2 $ $ ... $ $ B_M $

ゴールするまでにかかるターン数の期待値を出力せよ。 ただし、絶対誤差または相対誤差が $ 10^{-4} $ 以下ならば正解とみなされる。

### 制約 - $ 1≦N≦10^5 $ - $ 2≦M≦10^5 $ - $ 1≦A_i≦M $ - $ -10≦B_i≦M $ - $ B_1=B_M=0 $ ### Sample Explanation 1 最初のターンで出た目ごとに考えると以下のとおりである。 - 出た目が $ 1 $ の場合：$ 1 $ マス進み、$ 2 $ 番目のマスに止まる。このマスの効果により、$ 3 $ 番目のマスまで進む。次のターンでは何が出てもゴールできるため、ゴールには合計 $ 2 $ ターンかかる。 - 出た目が $ 2 $ の場合：$ 2 $ マス進み、$ 3 $ 番目のマスに止まる。このマスの効果により、$ 1 $ ターン休みとなる。次のターンは休みとなり、その次のターンでは何が出てもゴールできるため、ゴールには合計 $ 3 $ ターンかかる。 - 出た目が $ 3 $ の場合：$ 3 $ マス進み、$ 4 $ 番目のマスに止まる。すなわち、$ 1 $ ターンでゴールできる。 したがって、期待値は $ 2/3\ +\ 3/3\ +\ 1/3\ =\ 2 $ となる。