Cow Routing II#11186
Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for a 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 flies along a specific "route" consisting of two or more cities. For example, one plane might fly along a route that starts in 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 then disembark at any city that appears later on the route. She does not need 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 that route, regardless of how many cities she visits along it. Furthermore, Bessie may use each route at most once (that is, she cannot use one part of a route and later use another part of the same route).
Bessie wants to find the cheapest way to travel from her farm, located in city , to her tropical destination, located in city . Since she does not want to deal with a complicated itinerary, she wants to use at most two routes. Please help her determine the minimum total cost she must pay.
The first line contains , and n~(1 \le n \le 500).
The next lines describe the available routes, with two lines per route. The first line contains the cost of using the route (an integer from to ) and the number of cities along the route (an integer from to ). The second line contains a list of the cities in the order in which they appear along the route. Each city is identified by an integer in the range from to .
Output the minimum cost of an itinerary using at most two routes that allows Bessie to travel from city to city . If no such itinerary exists, output .
Use route to travel from city to city , and then use route to travel from city to city .
Example 1
Note that the only difference between this problem and the preceding Bronze problem is that here Bessie can use up to two routes, whereas in the preceding problem she could use only one.