The Great Masao has to read a lot to learn all he needs for his new job, so he has n boxes (numbered 0 …n − 1) full of books. Every box i is labelled with a number k_{i}, which is the increment of knowlegde achieved after reading any of the books in i. But be aware: reading some books can decrease your knowledge!
A box x can be a prerequisite of another box y. In this case, before Masao can read one or more books from box y, he must have read at least one book from box x.
Masao will do t times:
At every step, Masao will always take an optimal decision (to read or not to read). What is the maximum expected amount of knowledge that Masao can gain?
Input
Input is all integers, and consists of several cases. Every case begins with t, n, and the number of prerequisites p. Follow the n increments k_{i} (each is an integer number with absolute value at most 10^{6}). Follow p different pairs of x and y (with x ≠ y), indicating that x is a prerequisite of y. Books are numbered starting at zero. You can assume 0 ≤ t ≤ 50 and 1 ≤ n ≤ 10.
Output
For every case, print with two digits after the decimal point which is the maximum expected increment of knowledge of the Great Masao. The input cases have no precision issues.
Input
1 2 0 30 60 50 10 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 17 6 5 1000 -100 -100 -100 -100 -100 1 0 2 0 3 0 4 0 5 0
Output
45.00 50000.00 301.23