Cow Routing (Bronze)#11185
Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for vacation. Unfortunately, she discovers that only one airline, Air Bovinia, is willing to sell tickets to cows, and that these tickets are somewhat complicated.
Air Bovinia owns planes, each of which operates on a specific "route" consisting of two or more cities. For example, one plane might follow a route that starts at city , then flies to city , then to city , and finally to city . No city appears more than once on a route.
If Bessie chooses to use a route, she can board the plane at any city along the route and disembark at any city that appears later on the route. She does not have to board at the first city or disembark at the last city. Each route has a fixed cost, which Bessie must pay if she uses any part of the route, regardless of how many cities she visits along it.
Bessie would like to find the cheapest way to travel from her farm (in city ) to her tropical destination (city ). Since she does not want to deal with a complicated itinerary, she wants to use only a single route. Please help her determine the minimum cost she must pay.
The first line contains three integers A, B, n~(1 \le n \le 500).
The next lines describe the available routes, with two lines for each route.
The first line contains the cost of using the route (an integer in the range from to ) and the number of cities along the route (an integer in the range from to ).
The second line contains a list of the cities in order along the route. Each city is identified by an integer in the range from to .
Print the minimum cost of a single route that Bessie can use to travel from city to city . If no such route exists, print .
Although there is a cheaper two-route solution (using route to travel from city to city , and then route to travel from city to city ), Bessie is only allowed to use a single route. Therefore, she must use route , at a cost of .
Example 1