408110: GYM102986 F Norman's N&N's

Norman loves N&N's, a delicious chocolate-coated candy made by Nars, Inc. that comes in bags. Unfortunately, the factory that the N&Ns are made in is unreliable and fills the bags somewhat haphazardly. Nevertheless, Norman, being an avid fan of the N&N series of chocolates has discovered that there is an underlying distribution to the number of chocolates filled into each bag.

Norman has enough money to buy just one bag of N&N's. However, if he notices his bag has too few N&N's, he can return it to the store for a full refund and get a fresh bag, up to $$$k$$$ times due to Nars policy. Norman can immediately know how many there are in a bag just by holding one in his hand.

How many N&N's can Norman expect to get, assuming he returns bags optimally?

The first line contains $$$n$$$ and $$$k$$$, separated by a space, where $$$n$$$ is the number of distinct amounts of N&N's that a bag can have, $$$k$$$ is the number of times he can return a bag, $$$1 \le n \le 10^5, 0 \le k \le 10^4$$$.

The next line contains $$$n$$$ distinct space-separated integers $$$a_i$$$ where each of the $$$a_i$$$ are a possible number of N&N's the factory produces, and $$$0\le a_i \le 10^6$$$.

The next line contains $$$n$$$ space-separated numbers $$$p_i$$$ so that the probability the factory produces a bag with $$$a_i$$$ N&N's is $$$p_i$$$. $$$0< p_i < 1$$$, and $$$\sum_i p_i = 1$$$.

Output a single line, containing the expected number of N&N's Norman can get if he returns bags optimally. Your answer will be correct if it is within $$$10^{-6}$$$ of the correct answer.

3 0
1 3 2
0.4 3e-1 0.3

1.9

3 2
1 3 2
0.4 0.3 0.3

2.482