To read or not to read P47959


Statement
 

pdf   zip

html

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 ki, 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 ki 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 ki (each is an integer number with absolute value at most 106). Follow p different pairs of x and y (with xy), 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.

Public test cases
  • 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
    
  • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - SemiFinal
    Date
    2007-09-19