Before the final Normandy landings, the Allied and German intelligence agencies engaged in an unprecedented intelligence war surrounding the final landing site.

In this intelligence war, the Allied tactic was to use double agents embedded within the enemy to release false landing information to the heads of the enemy's intelligence agencies. These spies, already deep behind enemy lines, were the elite of the Allied intelligence department—loyal and reliable. However, how to select the right personnel and the best method of message transmission to ensure that the false information could be delivered to the German commanders as quickly, safely, and accurately as possible became the biggest problem plaguing the Allied intelligence chief. He needs your help.

The intelligence chief has provided the following operational data:

There are a total of $N$ of our best spies lurking behind enemy lines, numbered $1, 2, \dots, N$. Within the given operational time, at most one point-to-point contact can be made between any two people.

I will provide you with a table containing the security level $S_{ij}$ of the contact between any two spies $i$ and $j$, represented by a real number in $[0, 1]$; and the maximum number of messages $M_{ij}$ that can be transmitted between them during this contact, represented by a positive integer (if not mentioned in the table, there is no direct contact between spies $i$ and $j$).

The channels for transmitting false information from Allied headquarters to each spy are also not absolutely secure. We use a real number $AS_j$ in $[0, 1]$ to represent the security level of the contact between headquarters and spy $j$, and $AM_j$ to represent the maximum number of messages that can be transmitted between headquarters and spy $j$. For spies who do not have direct contact with headquarters, $AM_j = 0$ (and the $AS_j$ given in the table for them is meaningless).

Of course, the process of delivering false information from the spies to the desks of enemy intelligence officers is absolutely secure, meaning that either a spy does not have direct contact with the enemy intelligence department, or the security level of their contact is $1$ (i.e., completely reliable).

The intelligence department now plans to "leak" $K$ false messages to the Germans. The messages are first sent from headquarters to some of the $N$ spies at once, then propagated through the intelligence network between them, and finally delivered to the Germans by some of these $N$ spies.

For a single message, the transmission process is considered secure only if it passes through all intermediate stages and reaches the enemy intelligence department safely. Therefore, according to the multiplication principle, its security level $P$ is the product of the security levels of each transmission from the headquarters, through multiple relays, until it reaches the Germans.

For the entire plan, it is considered successful only when all $K$ messages have safely reached the Germans through the intelligence network without arousing any suspicion. Therefore, the reliability of the plan is the product of the security levels of all messages.

Clearly, the reliability of the plan depends on how these messages are transmitted through the intelligence network.

I need a plan that determines which people should transmit messages to whom, such that the final reliability of the plan is maximized.

You can use a computer to find this most reliable message transmission scheme.

Input

The input contains the Allied operational data table.

The first line contains two integers $N$ and $K$, representing the total number of spies and the total number of messages in the plan, respectively.

The second line contains $2N$ numbers. The first $N$ numbers are real numbers $AS_1, AS_2, \dots, AS_N$ (in the range $[0, 1]$); the next $N$ numbers are integers $AM_1, AM_2, \dots, AM_N$.

The third line contains $N$ integers, where the $i$-th integer ($i = 1, 2, \dots, N$) is $0$ if spy $i$ does not have contact with the enemy intelligence department, and $1$ if the spy does have contact with the enemy intelligence department.

Starting from the fourth line, each line contains 4 numbers: the positive integers $i$ and $j$ representing the spy IDs, the security parameter $S_{ij}$ for the contact between spies $i$ and $j$ (a real number in the range $[0, 1]$), and the maximum number of messages $M_{ij}$ that can be transmitted between $i$ and $j$ (for each line, $i < j$).

The last line contains two integers $-1$ $-1$, indicating the end of the input data.

$0 < N < 300$; $0 < K < 300$.

Output

The output contains only one line. This line contains a real number $P$, which is the reliability of the entire plan, rounded to 5 decimal places.

If the intelligence network cannot transmit $K$ messages to the Germans at all, the reliability of the plan is $0$.

(You may assume that if a plan exists, its reliability is greater than $1e-12$.)

Examples

Input 1

6 13
0.9 0.7 0.8 0 0 0 2 6 8 0 0 0
0 0 0 1 0 1
1 4 0.5 2
2 3 0.9 5
2 5 0.8 2
2 6 0.8 7
3 5 0.8 2
5 6 0.8 4
-1 -1

Output 1

0.00021184