폐회식

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

요약
0행 양끝의 두 입구에 있는 사람에게 좌석을 배정한다. 각 사람이 이동 거리 안에서 자신의 좌석에 도착할 수 있으면 YES를 출력한다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

Squanch Code Cup의 폐회식이 n개의 행과 각 행에 m개의 좌석이 있는 n × m 크기의 큰 회관에서 열린다. 각 좌석의 좌표는 (x, y)이고 (1 ≤ x ≤ n, 1 ≤ y ≤ m)이다.

회관에 입장하려는 두 줄의 사람들이 있다. k명은 (0, 0)에 서 있고 n·m - k명은 (0, m + 1)에 서 있다. 각 사람은 특정 좌석에 대한 티켓을 가지고 있어야 한다. (x, y)에 있는 사람 p가 좌석 (xp, yp)의 티켓을 가지고 있으면, 자기 좌석으로 가기 위해 |x - xp| + |y - yp|만큼 걸어야 한다.

각 사람은 체력을 가지고 있다. 체력은 그 사람이 기꺼이 걸을 수 있는 최대 거리이다. 모든 n·m개의 티켓을, 각 사람이 자기 좌석까지 갈 만큼의 체력을 가지도록 분배하는 것이 가능한지 판별하라.

입력

입력의 첫째 줄에 두 정수 n과 m이 주어진다 (1 ≤ n·m ≤ 104). 이는 회관의 크기이다.

둘째 줄에 여러 정수가 주어진다. 첫 번째 정수 k (0 ≤ k ≤ n·m)는 (0, 0)에 있는 사람 수이다. 뒤이어 오는 k개의 정수는 그곳에 있는 각 사람의 체력을 나타낸다.

셋째 줄에도 여러 정수가 주어진다. 첫 번째 정수 l (l = n·m - k)은 (0, m + 1)에 있는 사람 수이다. 뒤이어 오는 l개의 정수는 그곳에 있는 각 사람의 체력을 나타낸다.

사람의 체력은 n + m 이하인 양의 정수이다.

출력

설명한 방식대로 사람들 사이에 티켓을 분배하는 것이 가능하면 "YES"를, 그렇지 않으면 "NO"를 출력한다.

예제2

  1. 예제 1

    입력
    2 2
    3 3 3 2
    1 3
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2 2
    3 2 3 3
    1 2
    
    예상 출력
    NO