To read or not to read P47959

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:

• Choose a box i at random.
• If he can read one of the books of i (this will depend on the prerequisites) and if he decides to do so, he will read a book from i, thus adding k_i to his knowledge.

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⁶). 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.