Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS09ISO - Intergalactic Security Organization (Act IV)

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:
namei ci - the name of the i-th galaxy (a sequence of at most 10 characters) and the corresponding cost of a base - an integer 1 <= ci <= 100.

Next, m - the number of hypertunnels, and in each of the following m lines
namej1 namej2 - 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: namei - 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/Cp, where Cp 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).


Added by:kuszi
Date:2010-01-30
Time limit:0.200s-0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:High School Programming League 2009/10

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.