High School Programming League Problems Archive

Recently, Julia and Robert have made a series of experiments with their Network Resistance model and have discovered that a recommendation given by only one friend is often to weak to achieve real influence.

Thus, having the previous model with a social network of n members with a symmetric friendship relation (that is if A is a friend of B then also B must be a friend of A) and a positive integer W(A) associated with each member A, they are looking for a different subset of members.

Now the requested subset D' should have the property that every member of the network either is in D', or has at least half of his/her friends in D'. The sum of W(A) for all A in D' should be as small as possible.

Task: Write a program to find such subsets efficiently.

Input

Given: n - the number of social network members and in the next n lines:
name_i W(name_i) - the name of the i-th member (a sequence of at most 15 characters) and the corresponding integer 1 <= W(name_i) <= 250.

Next, m - the number of friendship relations, and in each of the following m lines
name_x name_y - the names of two linked members, name_x != name_y.

Output

In the first line print d', the number of members in D' and in the following d' lines: name_i - the name of the i-th member in D'. In the last line print one integer - the sum of W(A) for all A in D'.

Scoring

The score awarded to your program for a given test is computed as S/S_d', where S is the sum of W(A) for all A in the network, while S_d' is the sum of W(A) for all A in D'. The overall score of the program is the sum of scores obtained for correctly solved tests.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
5
Robert 12
Julia 23
Adam 1
Carol 10
Daniel 4
5
Robert Julia
Robert Carol
Adam Robert
Daniel Adam
Daniel Julia 

Output:
2 
Adam 
Robert
13

Scoring:
The exemplary solution will score 50/13 points.

Input data sizes

 t     n     m    l 
 1    100    99    2s
 2    100   101    2s
 3    100   105    2s
 4    100   114    2s
 5    100   130    2s
 6    300   299    5s   
 7    300   302    5s 
 8    300   311    5s
 9    300   339    5s
10    300   404    5s

 t - testcase number 
 n - the number of social network members
 m - the number of friendship relations
 l - time limit

Please note

• Till the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full set of test cases. (All earlier solutions will be rejudged).