Colorful Drink

면접 대비

시간 제한2초메모리 제한512 MB

요약
색과 밀도가 주어진 액체와 위에서 아래로의 색 요청 목록이 주어질 때, 요청한 각 층에 쓸 액체를 골라 밀도가 엄격히 감소하도록 만들 수 있는지 판단한다.
난이도

보통10점 중 6점

유형
그리디, 이분 탐색, 배열, 정렬
정답자
아직 제출이 없습니다

문제

Jambo Amusement Garden(JAG)에서는 여러 색 층으로 이루어진 무지개 음료를 판매한다. 이 무지개 음료는 밀도가 다른 여러 색 액체를 아래쪽부터 차례로 부어 만든다.

여러분은 이미 다양한 색과 밀도를 가진 색 액체를 여러 개 준비해 두었다. 이제 색 층이 지정된 음료 주문을 받는다. 제공할 무지개 음료는 다음 조건을 만족해야 한다.

  • 혼합한 색 액체를 한 층으로 쓸 수 없다. 즉, 서로 다른 두 색 액체를 섞어 새로운 색의 액체를 만들거나, 같은 색의 두 액체를 섞어 두 밀도 사이의 밀도를 가진 액체를 만들 수 없다.
  • 더 밀도가 큰 색 액체 위에는 밀도가 더 작은 색 액체만 올릴 수 있다. 즉, 밀도 yy인 색 액체 층 바로 위에 밀도 xx인 색 액체 층을 놓으려면 x<yx < y여야 한다.

여러분의 임무는 준비한 색 액체만으로 주어진 주문을 위 조건에 맞게 처리할 수 있는지 판별하는 프로그램을 작성하는 것이다.

입력

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

$N$
$C_1$ $D_1$
$\vdots$
$C_N$ $D_N$
$M$
$O_1$
$\vdots$
$O_M$

첫째 줄에는 준비한 색 액체의 개수를 나타내는 정수 NN (1≤N≤1051 \le N \le 10^5)이 주어진다. 다음 NN개 줄에는 CiC_i와 DiD_i (1≤i≤N1 \leq i \leq N)가 주어진다. CiC_i는 소문자 알파벳으로 이루어진 문자열로, ii번째로 준비한 색 액체의 색을 나타낸다. CiC_i의 길이는 1 이상 20 이하이다. DiD_i는 정수로, ii번째로 준비한 색 액체의 밀도를 나타낸다. DiD_i의 값은 1 이상 10510^5 이하이다. N+2N+2번째 줄에는 음료 주문의 색 층 개수를 나타내는 정수 MM (1≤M≤1051 \leq M \leq 10^5)이 주어진다. 다음 MM개 줄에는 OiO_i (1≤i≤M1 \leq i \leq M)가 주어진다. OiO_i는 소문자 알파벳으로 이루어진 문자열로, 음료 주문에서 위에서부터 ii번째 층의 색을 나타낸다. OiO_i의 길이는 1 이상 20 이하이다.

출력

준비한 색 액체 일부를 사용해 주문한 무지개 음료를 제공할 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

예제5

  1. 예제 1

    입력
    2
    white 20
    black 10
    2
    black
    white
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    2
    white 10
    black 10
    2
    black
    white
    
    예상 출력
    No
    
  3. 예제 3

    입력
    2
    white 20
    black 10
    2
    black
    orange
    
    예상 출력
    No
    
  4. 예제 4

    입력
    3
    white 10
    red 20
    white 30
    3
    white
    red
    white
    
    예상 출력
    Yes
    
  5. 예제 5

    입력
    4
    red 3444
    red 3018
    red 3098
    red 3319
    4
    red
    red
    red
    red
    
    예상 출력
    Yes