cho.sh

내일로 여행

일부 요금을 할인하는 철도 패스가 있을 때와 없을 때의 최소 이동 비용을 비교해 패스가 이득인지 판정한다.

보통4최단 경로그래프면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

승현이와 지학이는 여름방학에 국내 여행을 가기로 했다. 해외여행은 금전적으로 부담이 커서 두 사람은 한국의 여러 도시를 돌기로 했다. 한국에는 도시가 NN개 있고, 승현이는 그중 여행할 도시 MM개를 순서대로 정했다. 경로에서 같은 도시를 여러 번 지나도 되고, 여행을 시작하는 도시와 끝내는 도시는 같다.

두 도시 사이를 오가는 교통수단은 KK개 있다. 종류는 기차와 지하철, 버스, 택시, 비행기이고, 기차는 다시 무궁화호(Mugunghwa), ITX-새마을(ITX-Saemaeul), ITX-청춘(ITX-Cheongchun), KTX, S-Train, V-Train으로 나뉜다. 교통수단마다 한 번 이용하는 1인당 비용이 정해져 있다. 두 사람은 정해 둔 MM개의 도시를 차례대로 최소 비용으로 이동한다.

한편 코레일은 '내일로'라는 기차표를 판다. 방학 동안 청년은 1인당 RR원을 내고 내일로 티켓을 살 수 있다. 티켓을 사면 며칠 동안 무궁화호와 ITX-새마을, ITX-청춘을 무료로 이용하고, S-Train과 V-Train은 50% 할인된 가격으로 이용한다. KTX와 지하철, 그 밖의 교통수단에는 할인이 적용되지 않는다.

지학이를 도와 내일로 티켓을 사는 쪽과 사지 않는 쪽 중 어느 쪽의 총비용이 적은지 구하는 프로그램을 작성하라. 두 사람이 내는 금액은 서로 같으므로 1인 기준으로 비교하면 된다. 티켓을 사는 경우의 총비용은 RR원에 할인된 요금으로 계산한 최소 이동 비용을 더한 값이고, 사지 않는 경우의 총비용은 정가로 계산한 최소 이동 비용이다. S-Train과 V-Train의 할인 요금은 정수가 아닐 수 있으므로 두 총비용은 정확한 값으로 비교해야 한다.

입력

  • 첫째 줄에 도시의 수 NN (1≤N≤1001 \le N \le 100)과 1인당 내일로 티켓 가격 RR (1≤R≤10000001 \le R \le 1000000)이 주어진다.
  • 둘째 줄에 도시 NN개의 이름이 주어진다. 이름은 알파벳 대소문자로 이루어진 길이 20 이하의 문자열이다. 한국에는 이름이 같은 도시가 있을 수 있어서 둘째 줄에 같은 이름이 두 번 이상 나올 수 있고, 이름이 같은 도시는 모두 같은 도시로 본다.
  • 셋째 줄에 여행할 도시의 수 MM (1≤M≤2001 \le M \le 200)이 주어진다.
  • 넷째 줄에 여행할 도시 MM개의 이름이 방문 순서대로 주어진다. 모두 둘째 줄에 나온 도시다.
  • 다섯째 줄에 교통수단의 수 KK (1≤K≤100001 \le K \le 10000)가 주어진다.
  • 이어지는 KK개의 줄에 교통수단의 종류 TypeiType_i, 양 끝 도시 SiS_i와 EiE_i, 1인당 비용 CostiCost_i (1≤Costi≤1000001 \le Cost_i \le 100000)가 주어진다. TypeiType_i는 Subway, Bus, Taxi, Airplane, KTX, S-Train, V-Train, ITX-Saemaeul, ITX-Cheongchun, Mugunghwa 중 하나다. 모든 교통수단은 양방향으로 이용할 수 있고, 주어진 KK개의 교통수단만으로 모든 도시 사이를 오갈 수 있음이 보장된다.

출력

내일로 티켓을 사는 쪽의 총비용이 더 적으면 첫 줄에 Yes를, 그렇지 않으면 No를 출력한다. 두 총비용이 정확히 같으면 No를 출력한다.

힌트

첫 번째 예제에서 내일로 티켓을 사면 최소 비용은 다음과 같다.

  • Seoul에서 Jeonju까지 0원 (Seoul, Cheonan, Daejeon, Gwangju, Jeonju)
  • Jeonju에서 Suncheon까지 0원
  • Suncheon에서 Yeosu까지 0원
  • Yeosu에서 Suncheon까지 0원
  • Suncheon에서 Boseong까지 500원
  • Boseong에서 Jinju까지 1,500원 (Boseong, Suncheon, Jinju)
  • Jinju에서 Busan까지 1,000원 (Jinju, Suncheon, Jeonju, Gwangju, Daejeon, Daegu, Busan)
  • Busan에서 Seoul까지 0원 (Busan, Daegu, Daejeon, Cheonan, Seoul)
  • 이동 비용 3,000원에 티켓 40,000원을 더해 43,000원

티켓을 사지 않으면 최소 비용은 다음과 같다.

  • Seoul에서 Jeonju까지 12,500원 (Seoul, Cheonan은 지하철, Daejeon, Gwangju, Jeonju)
  • Jeonju에서 Suncheon까지 4,000원
  • Suncheon에서 Yeosu까지 1,500원
  • Yeosu에서 Suncheon까지 1,500원
  • Suncheon에서 Boseong까지 1,000원
  • Boseong에서 Jinju까지 3,000원 (Boseong, Suncheon, Jinju)
  • Jinju에서 Busan까지 1,500원
  • Busan에서 Seoul까지 18,500원 (Busan, Jinju, Seoul)
  • 합계 43,500원

43,000원이 43,500원보다 적으므로 답은 Yes다.