Scheduling Activities to Minimize Expected Loss

You are given n types of activities and k days. On each day, you must choose exactly one activity to do with your female friend. The i-th activity can be done at most c_i times and has a failure probability of a_i (i.e. if everything goes well, the activity makes her happy, but with probability a_i she remains unhappy). However, a special twist applies. Her mood only matters when it changes from happy to unhappy. Initially, before day 1, she is unhappy. On day 1 no loss occurs because she was unhappy the day before. From day 2 onward, if the activity on day d (with probability of failure a) is performed after a day when she ended up happy, then if the activity fails, she becomes unhappy and you incur a loss event. The expected number of loss events is therefore given by:

\( E = \sum_{d=2}^{k} \bigl[(1 - a_{x_{d-1}})\,a_{x_d}\bigr] \)

Your task is to choose an ordering (a sequence of activities, one per day) so that the expected number of loss events is minimized. Note that you are allowed to perform the same activity on consecutive days as long as you do not exceed its available count. Also, by careful analysis one can show that an optimal ordering is obtained if the activities are arranged in non-decreasing order of their failure probabilities, because for any adjacent pair the cost is \((1-a_i)a_j\) and swapping any two activities where the earlier one has a higher failure probability would only increase the cost.

Formally, you are given:

• Two integers n and k on the first line, where n is the number of activities and k is the total number of days.
• The second line contains n floating‐point numbers: a₁, a₂, ..., a_n, where a_i represents the probability that the i-th activity fails to make her happy.
• The third line contains n integers: c₁, c₂, ..., c_n, where c_i denotes the maximum number of times the i-th activity can be scheduled.

You must output a single floating‑point number representing the minimum expected number of loss events. Answers within an absolute or relative error of 1e-6 will be accepted.

inputFormat

The input consists of three lines:

1. The first line contains two integers n and k, separated by a space.
2. The second line contains n floating‑point numbers a₁ a₂ ... a_n.
3. The third line contains n integers c₁ c₂ ... c_n.

You may assume that \(\sum_{i=1}^{n} c_i \ge k\).

outputFormat

Output a single floating‑point number which is the minimum expected number of loss events. Your answer will be accepted if it has an absolute or relative error at most 1e-6.

sample

2 3
0.3 0.7
2 3

0.42