부품 테스트

INU전자의 엔지니어들이 새로운 전자부품을 개발했고, 앞으로 두 달 동안 이 부품들을 꼼꼼히 검토하고 테스트하려 합니다.

각 전자부품은 복잡도와 중요도에 따라 여러 클래스 중 하나로 분류됩니다. 같은 클래스에 속한 부품은 모두 같은 수의 검토자를 필요로 하며, 서로 다른 클래스는 서로 다른 수의 검토자를 필요로 할 수 있습니다. 하나의 클래스 안에는 여러 개의 부품이 있을 수 있습니다. 한 부품을 검토하는 검토자들은 서로 모두 달라야 합니다(같은 엔지니어가 한 부품을 두 번 검토할 수는 없습니다).

INU전자에는 여러 직급이 있습니다. 각 엔지니어는 정확히 하나의 직급을 가지며, 같은 직급의 엔지니어들은 검토할 수 있는 부품의 최대 개수가 모두 같습니다. 모든 엔지니어는 어떤 부품이든 검토할 수 있습니다. 한 엔지니어는 같은 클래스의 여러 부품이나 서로 다른 클래스의 부품을 검토할 수 있지만, 같은 부품을 두 번 이상 검토할 수는 없습니다.

모든 부품의 테스트를 두 달 안에 마칠 수 있는지 판단하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$ ($1 \le n \le 10{,}000$)과 $m$ ($1 \le m \le 10{,}000$)이 주어집니다. $n$은 부품 클래스의 수, $m$은 엔지니어 직급의 수입니다.

이어지는 $n$개의 줄에는 각 클래스의 정보가 두 정수 $j$ ($1 \le j \le 100{,}000$)와 $c$ ($0 \le c \le 100{,}000$)로 주어집니다. $j$는 그 클래스에 속한 부품의 개수이고, $c$는 그 클래스의 각 부품을 검토하는 데 필요한 서로 다른 검토자의 수입니다.

이어지는 $m$개의 줄에는 각 직급의 정보가 두 정수 $k$ ($1 \le k \le 100{,}000$)와 $d$ ($0 \le d \le 100{,}000$)로 주어집니다. $k$는 그 직급을 가진 엔지니어의 수이고, $d$는 그 직급의 엔지니어 한 명이 검토할 수 있는 부품의 최대 개수입니다.

입력의 끝은 두 정수가 모두 $0$인 줄로 표시됩니다.

각 테스트 케이스마다, 모든 부품의 검토를 마칠 수 있으면 $1$을, 그렇지 않으면 $0$을 한 줄에 출력하세요.