Flappy Bird is a popular casual mobile game. Players must continuously control the frequency of tapping the screen to adjust the bird's flight altitude, allowing it to pass through gaps in pipes on the right side of the screen. If the bird accidentally hits a pipe or falls to the ground, the game ends in failure.

To simplify the problem, we have adapted the game rules as follows:

1. The game interface is a 2D plane with length $n$ and height $m$, containing $k$ pipes (the width of the pipes is ignored).
2. The bird always moves within the game interface. The bird starts at any integer height at the leftmost side of the interface and completes the game upon reaching the rightmost side.
3. For each unit of time, the bird moves $1$ unit to the right along the horizontal axis, while its vertical movement is controlled by the player. If the screen is tapped, the bird rises by a height $X$. Multiple taps can be performed per unit of time, and their effects are cumulative. If the screen is not tapped, the bird descends by a height $Y$. The values of $X$ and $Y$ may vary depending on the bird's horizontal position.
4. The game fails if the bird's height reaches $0$ or if the bird hits a pipe. The bird cannot rise further if its height is $m$.

Determine whether it is possible to complete the game. If it is, output the minimum number of screen taps required; otherwise, output the maximum number of pipe gaps the bird can pass through.

Input

The first line contains three integers $n, m, k$, representing the length of the game interface, the height of the interface, and the number of pipes, respectively, separated by spaces.

The next $n$ lines each contain two integers $X$ and $Y$, separated by a space, representing the height $X$ the bird rises if the player taps the screen at horizontal position $0 \sim n-1$, and the height $Y$ the bird descends if the player does not tap the screen at that position.

The next $k$ lines each contain three integers $P, L, H$, separated by spaces. Each line represents a pipe, where $P$ is the horizontal coordinate of the pipe, $L$ is the height of the lower edge of the gap, and $H$ is the height of the upper edge of the gap (the input guarantees that all $P$ values are distinct, but they are not necessarily given in order).

Output

The output consists of two lines.

The first line contains an integer: $1$ if the game can be successfully completed, and $0$ otherwise.

The second line contains an integer: if the first line is $1$, output the minimum number of screen taps required to complete the game; otherwise, output the maximum number of pipe gaps the bird can pass through.

Examples

Input 1

10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3

Output 1

1
6

Input 2

10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10

Output 2

0
3

Note

As shown in the figure below, the blue line represents the bird's flight trajectory, and the red lines represent the pipes.

Constraints

For 30% of the data: $5 \leq n \leq 10, 5 \leq m \leq 10, k=0$, and it is guaranteed that there exists an optimal solution where the screen is tapped at most $3$ times per unit of time.

For 50% of the data: $5 \leq n \leq 20, 5 \leq m \leq 10$, and it is guaranteed that there exists an optimal solution where the screen is tapped at most $3$ times per unit of time.

For 70% of the data: $5 \leq n \leq 1000, 5 \leq m \leq 100$.

For 100% of the data: $5 \leq n \leq 10000, 5 \leq m \leq 1000, 0 \leq k < n, 0 < X < m, 0 < Y < m, 0 < P < n, 0 \leq L < H \leq m, L + 1 < H$.