Inspired by https://www.youtube.com/watch?v=eW_bMqcJXv0/

You are speedrunning a game with N successive levels. For each level i = 1,...,N, you have a target time t_i based on the "strats" you're going for, and a success probability p_i of achieving the respective target time (i.e., pulling off the strats).

(More precisely, the times t_i are the target durations of each level, not the "split" times. For example, if t_1 = 30 and t_2 = 20, you aim to finish level 1 in 30 seconds and level 2 in 20 seconds, i.e., you aim to finish level 2 at the 50-second mark from the start.)

The target time of each level is strict. You will either finish the level in exact time t_i (with probability p_i) or fail the level (with probability 1 - p_i). If you finish the level successfully, you move on to the next level if i < N or beat the game if i = N. If you fail the level, the failure occurs at the midpoint of the level in expectation, and you restart from level 1.

Taking into account all failures and restarts, how long will it take you to complete all N levels in their target times from start to finish, in expectation? In other words, how long will it take you to complete your speedrunning goal, in expectation?

Input

Your solution function expected_speedrun_time receives two arguments: times and probs. Argument times is a list of N elements corresponding to the level target times t_i, in seconds. Argument probs is a list of N elements corresponding to the level success probabilities p_i.

Output

The expected time in seconds until you complete all levels within their target times from start to finish, taking into account all failures and restarts.

Example

From the above video, Niftski's new SMB1 world record consists of N = 8 levels with target times times = [29.35, 33.60, 34.56, 28.64, 50.75, 35.67, 34.95, 47.12] and estimated success probabilities probs = [0.80, 0.70, 0.85, 0.05, 0.50, 0.35, 0.80, 0.80].

The correct answer is about 28431.47 seconds, or just under eight hours, which is roughly as long as it took for Niftski to achieve the record.