시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.7 초 256 MB 2 1 (50%) 1
문제
당신은 10개 유럽 왕실의 구성원들, 아르헨티나 축구 대표팀과 감독 디에고 마라도나 혹은 모든 튜링, 필즈상 수상자들과 같은 사람들을 만나본 적이 있는가? 우리는 CEOI 2010 폐막식에 전 세계의 많은 유명인을 초청했다. 안타깝게도 그중 극히 일부만 우리의 초대에 답신을 보냈고 답신의 내용은 정중한 거절이었다. 하지만 폐막식에 누가 나타날지는 모르니 카메라를 꼭 가져오길 바란다. 초청객들에 대한 경호가 최고로 중요하다는 점은 쉽게 생각해낼 수 있다. 문제는 경호원들을 어떻게 청중 사이에 배치하여 최상의 경호가 이루어지게 할 수 있는지 이다. 객석은 거대한 격자 형태로 정렬된 많은 좌석으로 이루어져 있다. 안전 규정에 따라 보안 전문가는 객석의 각 행과 열에 필요한 경호원의 숫자를 결정하였다. 객석의 각 행과 열에 필요한 경호원의 수가 주어진다. 이 정보는 아래에서 설명되는 형식에 따라 압축되어 전달된다. 각 행과 열에 정확하게 필요한 만큼의 경호원의 수를 배치할 수 있는 방법이 존재하는지 확인하라. 처음에 객석은 비어있다고 가정해도 된다, 즉 경호원을 원하는 위치에 어디든 배치할 수 있다. 한 좌석에는 최대 한 명의 경호원만 배치될 수 있다.
입력
입력은 행에 대한 설명으로 시작된다. 첫째 줄에 행의 묶음의 개수 $R$이 주어진다. 다음 $R$개의 줄에는 한 줄에 두 개의 정수가 주어지는데 차례대로 각 행에 필요한 경호원의 사람 수와 묶음에 들어있는 행의 개수이다. 다음에는 열에 대한 설명이 이어진다. 이어지는 줄에 열의 묶음의 개수 $C$가 주어진다. 다음 $C$개의 줄에는 한 줄에 두 개의 정수가 주어지는데 차례대로 각 열에 필요한 경호원의 사람 수와 묶음에 들어있는 열의 개수이다.
출력
조건들을 만족하게 만들 수 있다면 "1", 아니면 "0"을 출력한다 (따옴표는 출력하지 않는다.)
힌트
#### 제약조건 행의 제한조건에서 필요한 경호원의 총 사람수와 열의 제한조건에서 필요한 경호원의 총 사람수가 같다고 가정해도 된다. 총 경호원의 수는 $10^{18}$을 넘지 않는다. 입력의 모든 정수는 $1,000,000,000$을 넘지 않는다. 객석의 크기는 $1 \le R, C \le 200,000$ 을 만족시킨다. 테스트 케이스 중 $50$점에 해당하는 일부 서브태스크에서는 아래와 같은 조건을 만족시킨다 ``` 객석의 행의 개수는 2,000을 넘지 않는다. 객석의 열의 개수는 2,000을 넘지 않는다. 총 경호원의 수는 1,000,000을 넘지 않는다. ``` 나머지 중 $10$점에 해당하는 서브태스크에서는 $1 \le R, C \le 100$ 이다. 시간 제한은 $0.7$초, 메모리 제한은 $256MB$이다. #### 예제 입력 1 ``` 2 2 1 1 2 1 2 2 ``` #### 예제 출력 1 ``` 1 ``` 행은 두 개의 묶음으로 이루어져 있고 첫 묶음은 두 명의 경호원을 가지고 있는 하나의 행, 두 번째 묶음은 한 명의 경호원을 가지고 있는 두 개의 행으로 이루어져 있다. 열은 하나의 묶음인데 열 두 개가 각각 두 명의 경호원을 가지고 있어야 한다. 가능한 경호원의 배치 중 하나는 아래와 같다. ``` XX X. .X ``` #### 예제 입력 2 ``` 2 3 2 1 1 2 3 2 1 1 ``` #### 예제 출력 2 ``` 0 ``` 두 개의 행에서 경호원을 꽉 채워야 하므로 모든 열은 적어도 두 명의 경호원을 가지게 되는데 이는 마지막 열이 한 명의 경호원을 가져야 한다는 조건에 모순된다.