Maximizing the Reliability of Espionage Communications

During the days preceding the final Normandy landing, the Allied and German intelligence services engaged in an unprecedented information war over the final landing site. The Allied strategy was to use double agents embedded behind enemy lines to transmit fake landing orders to the enemy commanders. However, choosing which agents to use and how to route the messages in order to deliver them quickly, securely, and accurately became a major problem for the Allied intelligence chief. You are tasked with helping him.

There are N of the best spies hidden behind enemy lines, numbered 1,2,…,N. Within the given operational time, any two spies may communicate directly at most once. For any two spies i and j that can directly contact each other, you are given:

• a safety level S_i,j (a real number in [0,1]) describing how secure their communication is, and
• an integer M_i,j indicating the maximum number of messages that can be exchanged during that contact.

The messages are first transmitted from headquarters (HQ) to some spies. For each spy j, if HQ is able to contact spy j directly, the safety level of that link is given by AS_j (a real number in [0,1]) and the maximum number of messages that can be sent is AM_j (a positive integer). For any spy that is not in direct contact with HQ, AM_j = 0 (and the corresponding AS_j is meaningless).

Finally, when a spy delivers a message to the enemy intelligence, the transfer is absolutely safe (i.e. if a spy and the enemy communicate directly, the safety level is 1). The operation involves transmitting K fake messages. The messages are sent from HQ to some spies, then forwarded among spies via direct contacts, and finally some spies deliver them to the enemy. For each message, if the communication chain is p₀ → p₁ → … → p_t (with p₀ being HQ and p_t the enemy), then the overall safety level of that message is given by the product

The overall plan is successful if all K messages safely reach the enemy intelligence. In other words, the reliability of the plan is the product of the safety levels of each individual message. Your task is to choose a routing scheme – that is, which spies should receive the messages from HQ and how the messages should be forwarded between spies – so that the overall plan reliability is maximized.

Note: Maximizing the product of probabilities is equivalent to maximizing the sum of their logarithms. Thus it may be useful to work with logs, remembering that for an edge with safety s the corresponding cost is -\ln(s) (with safety levels given in latex format as $s$ and cost as $-\ln(s)$).

inputFormat

The input is given as follows:

N E K
// Next E lines: each contains the description of a direct contact between spies
// Each line contains: i j S M
// meaning that spies i and j can communicate directly with safety S (a real number in [0,1]) and capacity M (a positive integer).
i1 j1 S1 M1
...
iE jE SE ME
// Next N lines: each line describes the direct connection from headquarters to a spy
// Each line contains: AS AM
// For spy j (1-indexed), AS is the safety level (a real number in [0,1]) for the HQ→spy link and AM is the maximum number of messages that can be sent on this link.
// For spies not in direct contact with HQ, AM will be 0.
AS1 AM1
AS2 AM2
...
ASN AMN

It is guaranteed that 1 ≤ N ≤ 100, 0 ≤ E ≤ N*(N-1)/2, 1 ≤ K ≤ 100, 0 ≤ S, AS ≤ 1, and M, AM are positive integers (with AM = 0 for spies not directly in contact with HQ).

outputFormat

Output a single floating-point number indicating the maximum overall plan reliability achievable. If it is impossible to send all K messages through the network, output 0. The answer should be printed with at least 6 digits after the decimal point.

sample

3 3 2
1 2 0.9 2
2 3 0.8 1
1 3 0.5 1
0.95 2
0.9 1
0.0 0

0.405000