Description

Best Flight to Stockholm 

Selina is a NTHU student who will be going on an exchange to Sweden. She wants to search for the best flight from Taipei to Stockholm using Skyscanner. The things she will take into consideration are:

• Price
• Total flying time
• Number of transfer stops

When applying the Price filter, she wants the BEST flight to have the lowest price; for total flying time, she wants the flying time to be as short as possible so that she can arrive in Stockholm ASAP; and for the number of transfer stops, she wants the flight with the fewest transfer stops. She will apply different combinations of filters for each search. Can you help her find the BEST flight every time? Let’s Goooo!!!

For the homework you are not allowed to use STL.

Input

The first line has two integer m, n which are the number of flight connections and number of filters. The next m lines are the flight connections. In each line, there are:

• 2 strings, from and to
• 2 integers price, and time

Which are the flight ticket price and its flying duration flying from city from to city to.

Note that, there may be duplicated from and to pairs with different prices and different times, since there are many airlines that fly to the same place.

After that, the next n lines are the filters to apply:

• 1 stands for price
• 2 stands for total flying time
• 3 stands for number of transfer stops.

If there is more than one filter, the one that appears first should be considered first. For example, 1 2 means that the cheapest flights should be considered first, followed by the total flying time.

Output

First line, prints the price value of the BEST flight from Taipei to Stockholm. Next line, prints the route from Taipei to Stockholm. Each city in the route use -> to separate. It is guaranteed that a route from Taipei to Stockholm always exists.

Constrains

1≤ m ≤ 10⁵

1≤ n ≤ 3

1 ≤ price, time ≤ 10⁶

1 ≤ Length of from and to ≤ 256

1 ≤ number of cities ≤ 256

Sample Input  Download

Sample Output  Download

Tags

Discuss