High School Programming League Problems Archive

Long, long time ago High School Programming League contestants helped ISO (Intergalactic Security Organization) to plan their bases allocation system. But now, after billions billions years, when new galaxies and hypertunnels has been descovered it appeared that ISO requires to extend their system. It appeared that not only each galaxy should be close to the nearest base but also bases (due to security reasons) should be placed in the one hypertunnel distance to the nearest base. Now, the task is to design a placement of new bases so as to minimize the cost of the whole project. Given all the galaxies, the costs of bases (dependent on the galaxy of their location), the arrangement of hypertunnels, and the location of existing bases you must select some galaxies as locations of new ISO bases.

Input

Given: n - the number of galaxies and in the next n lines:
name_i c_i - the name of the i-th galaxy (a sequence of at most 10 characters) and the corresponding cost of a base - an integer 1 <= c_i <= 100.

Next, m - the number of hypertunnels, and in each of the following m lines
name_j1 name_j2 - the names of two galaxies connected by the tunnel.

In the end x - the number of existing bases is given and in following x lines their locations.

Output

First output k the number of bases and in the following k lines: name_i - the name of the i-th galaxy to place the ISO base at, and in the last line: cost the total cost of all the new bases.

Scoring

The score awarded to your program for a given test is computed as C/C_p, where C_p is the cost obtained by your program, and C is cost of building bases in all galaxies. 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 contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
8
SmallCloud 5
LargeCloud 3
LeoA 3
CetusDwarf 5
MilkyWay 4
Andromeda 4
NGC185 3
AndI 6
9
SmallCloud LargeCloud 
LargeCloud Andromeda
Andromeda CetusDwarf
CetusDwarf AndI
CetusDwarf MilkyWay
AndI MilkyWay
AndI NGC185
MilkyWay LeoA
LeoA SmallCloud
2
LeoA
NGC185

Output I:
3
SmallCloud
LargeCloud
AndI
14

Scoring: Cost C for this test is equal to 27, the exemplary solution will score 27/14 points.

Output II:
3
SmallCloud
LargeCloud
Andromeda
12

Scoring:

This answer would be judged as wrong because the base in NGC185 is more than one hypertunnel away from the nearest of the bases.

Input data sizes

Approximate test data sizes are given below.

 t     n     m    x    l 
 1    10    15    2    1s
 2    20    30    2    2s
 3    30    40    3    2s
 4    40    70    4    2s
 5    60    90    6    2s
 6    90   130    9    2s
 7   100   130   10    2s
 8   110   170   10    2s
 9   120   130   11    2s
10   130   140   12    2s
11   140   180   15    2s
12   150   260   15    2s
 t - testcase number 
 n - the number of galaxies
 m - the number of hypertunnels
 x - the number of existing bases
 l - time limit

Please note

• Till the last week of the series, all submitted codes will be visible to all users and tested on selected 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).