Component Testing

The engineers at INU Electronics have developed some new electronic components, and over the next two months they plan to thoroughly review and test them.

Each component is sorted into one of several classes according to its complexity and importance. Every component in the same class needs the same number of reviewers, while different classes may need different numbers of reviewers. A single class may contain many components. The reviewers of any one component must all be distinct (the same engineer cannot review a single component twice).

INU Electronics has several ranks. Each engineer holds exactly one rank, and all engineers of the same rank can review the same maximum number of components. Every engineer is able to review any component. An engineer may review several components of the same class or components of different classes, but may never review the same component more than once.

Determine whether all of the components can be tested within two months.

The input consists of several test cases.

The first line of each test case contains two integers $n$ ($1 \le n \le 10{,}000$) and $m$ ($1 \le m \le 10{,}000$), where $n$ is the number of component classes and $m$ is the number of engineer ranks.

Each of the next $n$ lines describes one class with two integers $j$ ($1 \le j \le 100{,}000$) and $c$ ($0 \le c \le 100{,}000$): $j$ is the number of components in that class, and $c$ is the number of distinct reviewers required to review each component of that class.

Each of the next $m$ lines describes one rank with two integers $k$ ($1 \le k \le 100{,}000$) and $d$ ($0 \le d \le 100{,}000$): $k$ is the number of engineers holding that rank, and $d$ is the maximum number of components a single engineer of that rank can review.

The input ends with a line containing two zeros.

For each test case, print $1$ on its own line if every component can be reviewed, and $0$ otherwise.