프리즘 연구소에는 이름으로 구분되는 N개의 관문이 있다. 연구소의 작업 스크립트는 M개의 관문 이름을 순서대로 담고 있으며, 스크립트를 실행할 때는 첫 번째 관문에서 시작해 두 번째 관문, 세 번째 관문, … 순서로 차례대로 이동해야 한다. 같은 관문 이름이 여러 번 등장할 수 있다.

관문 사이에는 K개의 양방향 연결 규칙이 있다. 각 연결 규칙에는 등급 코드와 기본 비용이 붙어 있다. 스크립트의 각 연속한 두 관문 사이를 이동할 때는 주어진 연결 규칙들을 이용해 비용이 최소가 되도록 이동한다.

연구소에서는 R을 지불하면 한 번의 작업 동안 사용할 수 있는 프리즘 인증권을 발급한다. 이 인증권을 사용하면 등급 코드가 Mugunghwa, ITX-Saemaeul, ITX-Cheongchun인 연결은 비용이 0이 되고, S-Train, V-Train인 연결은 비용이 절반이 된다. 그 밖의 등급 코드는 비용이 변하지 않는다.

인증권을 발급받는 것이 전체 작업 비용을 줄이는지 판단하는 프로그램을 작성하시오. 인증권을 사용한 총비용에는 발급 비용 R이 포함된다.

입력

첫 번째 줄에는 관문의 수 N(1 ≤ N ≤ 100)과 인증권의 가격 R(1 ≤ R ≤ 1,000,000)이 주어진다.

두 번째 줄에는 N개의 관문 이름이 주어진다. 관문 이름은 알파벳 대소문자로 구성된 길이 20 이하의 문자열이다.

세 번째 줄에는 작업 스크립트에 적힌 관문의 수 M(1 ≤ M ≤ 200)이 주어진다.

네 번째 줄에는 차례대로 방문해야 하는 M개 관문의 이름이 주어진다. 이 이름들은 앞서 주어진 N개의 관문 이름 중 하나이다.

다섯 번째 줄에는 연결 규칙의 수 K(1 ≤ K ≤ 10,000)가 주어진다.

마지막 K개의 줄에는 연결 규칙의 정보가 주어진다. 줄마다 등급 코드 Typei, 양 끝 관문 Si, Ei, 기본 비용 Costi (1 ≤ Costi ≤ 100,000)가 주어진다. Typei는 Subway, Bus, Taxi, Airplane, KTX, S-Train, V-Train, ITX-Saemaeul, ITX-Cheongchun, Mugunghwa 중 하나이다. 모든 관문은 주어진 연결 규칙들을 이용하여 서로 도달할 수 있음이 보장된다.

같은 이름의 관문이 두 번 이상 주어질 수 있다. 이 경우 같은 이름을 가진 관문들은 모두 하나의 관문으로 취급한다.

출력

인증권을 발급받는 편이 발급받지 않는 편보다 총비용이 작으면 Yes를 출력하고, 그렇지 않으면 No를 출력한다. 두 총비용이 정확히 같아도 No를 출력한다.

예제 입력 1

14 40000
Boseong Busan Changwon Cheonan Chuncheon Daegu Daejeon Gwangju Jeonju Jinju Masan Seoul Suncheon Yeosu
9
Seoul Jeonju Suncheon Yeosu Suncheon Boseong Jinju Busan Seoul
23
KTX Seoul Busan 20000
KTX Seoul Gwangju 12000
KTX Gwangju Yeosu 8000
KTX Seoul Jinju 17000
ITX-Saemaeul Seoul Cheonan 7000
ITX-Cheongchun Seoul Chuncheon 3000
V-Train Chuncheon Daegu 10000
Subway Seoul Cheonan 2000
ITX-Saemaeul Cheonan Daejeon 4000
ITX-Saemaeul Daejeon Daegu 10000
ITX-Saemaeul Daegu Busan 7000
Mugunghwa Daejeon Daegu 6000
Mugunghwa Daejeon Gwangju 5000
Mugunghwa Gwangju Jeonju 1500
Mugunghwa Jeonju Suncheon 4000
Mugunghwa Suncheon Yeosu 1500
S-Train Busan Changwon 3000
S-Train Changwon Masan 1000
S-Train Masan Jinju 2000
S-Train Jinju Suncheon 2000
S-Train Suncheon Boseong 1000
Bus Busan Jinju 1500
Bus Suncheon Jinju 4000

예제 출력 1

Yes

예제 입력 2

5 50000
Seoul Cheonan Daejeon Daegu Busan
3
Seoul Busan Seoul
5
ITX-Saemaeul Seoul Cheonan 7000
ITX-Saemaeul Cheonan Daejeon 4000
ITX-Saemaeul Daejeon Daegu 10000
ITX-Saemaeul Daegu Busan 7000
KTX Seoul Busan 24999

예제 출력 2

No

힌트

예제 1에서 인증권을 적용하면 스크립트 이동에 드는 최소 비용은 3,000이고, 여기에 인증권 가격 40,000을 더한 총비용은 43,000이다. 인증권을 적용하지 않을 때의 최소 총비용은 43,500이므로 Yes가 출력된다.