HopOnHopOff services are a great way to explore a city in a flexible manner, at your own pace.
Sightseeing Inc want to offer tourists the option to create their own routes based on their interests. Sightseeing Inc have a list of places of interests(POIs) for each city, tagged with one or more categories.
Over the years, they've also identified the best paths for sightseeing between the various POIs, so their buses only take these paths. They have hired you to design an algorithm which takes as input the tagged list of POIs, the list of direct paths (with fares) between various POIs and the categories of interest of the user.
The algorithm should then give the maximum number of places which can be covered by a route, along with the total fare. If more than one such route exists, the algorithm should pick the best route based on minimal total fare. Since the route will not contain any POI which does not match the user's interests. A ticket between any two POIs allows unlimited travel between those POIs.
The first line of the input contains a single integer T denoting the number of test cases.
The first line of each test case contains two integers P and R separated by a space where P denotes the number of POIs and R denotes the number of direct routes between these POIs.
This is followed by P lines, each line containing the name of the place followed by it's categories, all separated by a space.
This is followed by R lines denoting R paths, each containing two places and the fare between them, all separated by a space.
The final line of each test case contains one or more categories of interest of the user separated by a space.
For each test case, output a single line containing two integers N and D separated by a space where:
N is the maximum number of places which will be covered by a single route
C is the total fare
1 <= T <= 100
1 <= P <= 50
1 <= R <= 200
1 <= Total number of categories <= 20
Length of each line will not be more than 80 characters
ChandniChowk Shopping Historical Food
ChandniChowk QutubMinar 15
ChandniChowk RedFort 4
QutubMinar SarojniNagar 10
SarojniNagar HumayunTomb 10
HumayunTomb IndiaGate 10
Explanation of Input
Line 1: T = 1
Line 2: P = 6, R = 5
Lines 3 to 8: (6 lines) the POI's along with it categories for e.g. ChandniChowk is the name of the place followed by categories of this place i.e. Shopping Historical & Food
Lines 9 to 13: (5 lines) the paths between POI’s and the fare between them. For e.g. ChandniChowk QutubMinar 15 denotes ChandniChowk and Qutub Minar have a direct path with fare 15
Line 14: contains categories in which traveler is interested to visit, Historical
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions