4698번 - 부품 테스트 다국어

INU전자의 엔지니어들은 얼마 전 새로운 전자부품을 개발했습니다. 그들은 앞으로 두 달 동안 새로운 전자부품을 철저히 검토하고 테스트 할 계획입니다. 각 전자부품은 복잡도와 중요성에 따라 여러 개의 다른 클래스로 분류됩니다. 다른 클래스의 부품테스트에는 다른 수의 검토자가 필요하지만 동일한 클래스의 부품테스트에는 항상 같은 수의 검토자가 필요합니다. 또한 하나의 클래스 안에 여러개의 부품이 존재할 수 있습니다.

INU전자에는 여러 가지 직급이 있습니다. 각 엔지니어 하나의 직급을 보유합니다 (직급이 여러개인 엔지니어는 없습니다). 같은 직급을 가지고있는 모든 엔지니어는 검토할 수 있는 부품의 수에 동일한 제한을 두고 있습니다. 엔지니어들은 모두 어떠한 부품검토에도 지정될 수 있으며 모든 부품의 검토에 대한 수행능력이 있습니다. 엔지니어는 같은 클래스내의 여러 부품과 다른 클래스에 속하는 부품들을 검토 할 수 있지만, 동일한 부품을 두 번 이상 검토 할 수 없습니다.

INU 전자의 엔지니어들은 모든 부품의 테스트를 두 달내에 완료할 수 있을까요?

입력에는 여러 가지 테스트 케이스가 있습니다.

각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n (1 ≤ n ≤ 10,000)과 m (1 ≤ m ≤ 10, 000)이 포함됩니다. 여기서 n은 전자부품 클래스 수이고 m은 엔지니어 직급의 수입니다.

다음 n 행에는 두 개의 정수 j (1 ≤ j ≤ 100,000)와 c (0 ≤ c ≤ 100,000)가 전자부품에 대한 정보를 알려줍니다. j는 각 클래스에 속하는 전자부품의 수를 나타내고, c는 해당 클래스에 최소한 c 명의 다른 검토자가 필요함을 나타냅니다.

다음 m 행은 각각이 두 개의 정수 k (1 ≤ k ≤ 100,000)와 d (0 ≤ d ≤ 100,000)를 포함하며, m개의 직급에 대한 정보를 알려줍니다. 각 행의 k는 해당 직급을 가진 k 명의 엔지니어가 있음을 나타내고, 그 직급의 엔지니어가 검토할 수 있는 부품의 수는 d입니다.

입력은 두 개의 0이있는 행으로 끝납니다.

전자부품 검토를 마칠 수 있으면 1을 포함하는 한 줄을 인쇄하고, 그렇지 않으면 0을 각 테스트 사례에 대해 인쇄하십시오.