F. Forever on a Bicycle
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

National Taiwan University's campus is quite large, and as a commuting student, Wiwiho doesn't want to walk 15 minutes to her department after a long commute. Therefore, she decides to use the Ubike facilities scattered around the campus.

However, there's a significant flaw she often overlooks. After successfully borrowing a Ubike from a station, she frequently finds that the stations near her department have no available slots when she arrives, forcing her to cycle to a more distant station and then walk a longer distance to her destination, defeating the purpose.

As a competitive programming contestant, Wiwiho decides to plan an optimal route to reach her department as quickly as possible. She selects $$$N$$$ stations on the NTU campus, numbered from $$$1$$$ to $$$N$$$, and plans $$$M$$$ routes between these stations. Each route is defined by three numbers $$$u_i, v_i, w_i$$$, representing a route between station $$$u_i$$$ and $$$v_i$$$ with a cycling time of $$$w_i$$$, regardless of direction.

Because returning a bike depends on luck, for each station, Wiwiho has estimated parameters $$$p_i, q_i, d_i$$$ through statistical data. Initially, all stations are in an "unknown state". When she arrives at station $$$i$$$ which is in an unknown state, she can try to observe the station and use the following strategy:

  • Whenever Wiwiho observes at station $$$i$$$, there's a probability $$$p_i$$$ that the station has an available slot.
  • If there's an available slot, she can return the bike and walk to her department in $$$d_i$$$ time.
  • If there's no available slot, Wiwiho can choose to cycle away immediately. After this, she will turn that station into a "full state".
  • If there's no available slot but Wiwiho chooses not to cycle away, she can wait an expected $$$q_i$$$ time for a slot to become available, then walk to her department in $$$d_i$$$ time. Note that during this $$$q_i$$$ time, Wiwiho cannot leave the station because returning a bike requires queuing.

Besides, when Wiwiho arrives at station $$$i$$$ which is in a full state, she can still choose not to cycle away, and wait an expected $$$q_i$$$ time for a slot to become available, then walk to her department in $$$d_i$$$ time.

Note that Wiwiho can choose not to observe a station when she passes through it.

To simplify the problem, assume that the probabilities and expected values for each station are independent, meaning stations do not influence each other's parameters.

Can you help Wiwiho find the minimum expected time to successfully return a bike and walk to her department if she borrows a Ubike from station $$$1$$$? Note that although Wiwiho can choose to return the bike at station $$$1$$$, she must follow the aforementioned rules, meaning she only has a probability $$$p_1$$$ of immediately returning the bike there.

Input

The first line contains two integers $$$N, M$$$, representing the number of stations, and the number of routes Wiwiho selected.

The second line contains $$$N$$$ floating-point numbers $$$p_1, p_2, \ldots, p_N$$$, representing the probability of finding an available slot at station $$$i$$$ when Wiwiho arrives.

The third line contains $$$N$$$ floating-point numbers $$$q_1, q_2, \ldots, q_N$$$, representing the expected queuing time at station $$$i$$$ if no slot is available upon arrival.

The fourth line contains $$$N$$$ floating-point numbers $$$d_1, d_2, \ldots, d_N$$$, representing the time required to walk from station $$$i$$$ to her department.

The next $$$M$$$ lines each contain two integers and one floating-point number $$$u_i, v_i, w_i$$$, representing a route connecting station $$$u_i$$$ and station $$$v_i$$$, with a cycling time $$$w_i$$$ between them.

  • $$$1 \leq N \leq 18$$$
  • $$$0 \leq M \leq \frac{N \times (N-1)}{2}$$$
  • $$$0 \leq d_i, w_i, q_i \leq 1000$$$
  • $$$0 \leq p_i \leq 1$$$
  • All floating-point numbers will be given to three decimal places.
  • No two routes connect the same pair of stations.
Output

Output a single floating-point number representing the minimum expected time for Wiwiho to successfully return a bike and walk to her department after borrowing a Ubike from station $$$1$$$.

Your answer will be accepted if the absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$$$.

Examples
Input
4 4
0.800 0.500 0.200 0.600
3.000 3.000 5.000 2.000
15.000 5.000 1.000 2.000
1 2 3.141
2 3 2.718
1 3 7.654
3 4 1.414
Output
8.78560000000000052012
Input
11 13
0.800 0.800 0.900 0.900 0.400 0.200 0.200 0.200 0.250 0.400 0.400
1.000 2.000 2.000 2.000 3.000 4.000 4.000 4.000 2.000 1.000 1.000
15.000 12.000 11.000 9.000 3.000 0.000 0.000 0.000 2.000 5.000 4.000
1 2 1.000
1 4 2.333
2 3 0.333
3 4 0.666
4 5 2.000
5 6 1.000
5 10 1.666
6 7 0.333
6 8 0.333
6 9 0.666
7 8 0.333
9 10 1.000
9 11 0.666
Output
7.31551200000000090284