High School Programming League Problems Archive

You are given a group G of n people and a symmetric relation R between them (we interpret pRq for example as follows: p is able to work with q and vice versa). Your task is to partition as large a subset of G as possible into working groups of three people in such a way that for every triple (p,q,r), the group leader p is able to work with the other two members of the group (i.e., pRq and pRr).

Input

Given: n - the number of people and in the next n lines:
name_i W(name_i) - the name of the i-th person (a sequence of at most 15 characters) and the corresponding integer 1 <= W(name_i) <= 100.

Next, m - the number of elements in relation R, and in each of the following m lines
name_x name_y - the names of two related people, name_x != name_y.

Output

In the first line print g, the number of groups in your solution and in the following g lines: name_p name_q name_r - names of people in the consecutive group (the name of the leader first). In the last line print one integer S_g- the sum of 2*W(name_p)+W(name_q)+W(name_r) taken over all groups.

Scoring

The score awarded to your program for a given test is simply S_g. 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:
7
Adam 4
Carol 3
Daniel 3
Robert 4
Julia 5
Frank 3
Henry 5
7
Adam Carol
Carol Daniel
Carol Julia
Adam Robert
Robert Julia
Julia Frank
Robert Henry


Output:
2 
Julia Carol Frank
Robert Adam Henry 
33

Scoring:
The exemplary solution will score 33 points.

Input data sizes

 t     n     m    l 
 1    120   119    2s
 2    120   121    2s
 3    120   123    2s
 4    120   130    2s
 5    120   145    2s
 6    270   269    5s
 7    270   287    5s
 8    270   292    5s
 9    270   312    5s
10    270   341    5s

 t - testcase number 
 n - the number of people
 m - the number of 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).