Nailro Rail Pass Trip

Seunghyeon and Jihak decided to travel inside Korea over summer vacation. Going abroad costs too much, so the two of them will tour several Korean cities instead. Korea has $N$ cities, and Seunghyeon picked $M$ of them as the itinerary, in visiting order. The route may pass through the same city more than once, and the city where the trip starts is the city where it ends.

$K$ transport connections run between pairs of cities. The kinds are train, subway, bus, taxi and airplane, and the train kinds are Mugunghwa, ITX-Saemaeul, ITX-Cheongchun, KTX, S-Train and V-Train. Every connection has a fixed fare per person per ride. The two of them move through the $M$ chosen cities in order at the lowest possible cost.

Korail also sells a rail pass called Nailro. During vacation a young traveller buys one for $R$ won per person. With the pass, Mugunghwa, ITX-Saemaeul and ITX-Cheongchun rides are free for several days, and S-Train and V-Train rides cost 50% of the fare. KTX, the subway and every other kind get no discount.

Help Jihak work out which choice costs less, buying the pass or skipping it. Both travellers pay the same amount, so compare the cost for one person. The total with the pass is $R$ plus the minimum travel cost computed from the discounted fares. The total without the pass is the minimum travel cost computed from the full fares. A 50% S-Train or V-Train fare is not always an integer, so compare the two totals exactly.

• The first line has the number of cities $N$ ($1 \le N \le 100$) and the price of one Nailro pass $R$ ($1 \le R \le 1000000$).
• The second line has the names of the $N$ cities. A name is a string of at most 20 upper and lower case letters. Two Korean cities can share a name, so the second line may repeat a name, and cities with the same name are the same city.
• The third line has the number of cities on the itinerary $M$ ($1 \le M \le 200$).
• The fourth line has the names of those $M$ cities in visiting order. Each one appears on the second line.
• The fifth line has the number of transport connections $K$ ($1 \le K \le 10000$).
• Each of the next $K$ lines has a connection kind $Type_i$, its two end cities $S_i$ and $E_i$, and the fare per person $Cost_i$ ($1 \le Cost_i \le 100000$). $Type_i$ is one of Subway, Bus, Taxi, Airplane, KTX, S-Train, V-Train, ITX-Saemaeul, ITX-Cheongchun, Mugunghwa. Every connection runs in both directions, and the $K$ given connections are guaranteed to reach every city from every other city.

Print Yes on one line if buying the Nailro pass gives the smaller total cost, and No otherwise. Print No when the two totals are exactly equal.

In the first example the minimum cost with the Nailro pass is this.

• Seoul to Jeonju for 0 won (Seoul, Cheonan, Daejeon, Gwangju, Jeonju)
• Jeonju to Suncheon for 0 won
• Suncheon to Yeosu for 0 won
• Yeosu to Suncheon for 0 won
• Suncheon to Boseong for 500 won
• Boseong to Jinju for 1,500 won (Boseong, Suncheon, Jinju)
• Jinju to Busan for 1,000 won (Jinju, Suncheon, Jeonju, Gwangju, Daejeon, Daegu, Busan)
• Busan to Seoul for 0 won (Busan, Daegu, Daejeon, Cheonan, Seoul)
• 3,000 won of travel plus the 40,000 won pass, so 43,000 won

Without the pass the minimum cost is this.

• Seoul to Jeonju for 12,500 won (Seoul, Cheonan by subway, Daejeon, Gwangju, Jeonju)
• Jeonju to Suncheon for 4,000 won
• Suncheon to Yeosu for 1,500 won
• Yeosu to Suncheon for 1,500 won
• Suncheon to Boseong for 1,000 won
• Boseong to Jinju for 3,000 won (Boseong, Suncheon, Jinju)
• Jinju to Busan for 1,500 won
• Busan to Seoul for 18,500 won (Busan, Jinju, Seoul)
• 43,500 won in total

43,000 won is less than 43,500 won, so the answer is Yes.