Problem Background

NOIP2014 Senior Group D1T3

Problem Description

Flappy Bird is a popular casual mobile game where players need to control the frequency of tapping the screen to adjust the bird's flight height, allowing it to pass through the gaps in the pipes on the right side of the screen. If the bird hits a pipe or falls to the ground, the game is over.

To simplify the problem, we have modified the game rules:

The game interface is a 2D plane with a length of $n$ and a height of $m$, containing $k$ pipes (ignoring the width of the pipes).

The bird always moves within the game interface. The bird starts at any integer height on the leftmost side of the interface and completes the game when it reaches the rightmost side.

The bird moves one unit to the right per unit time, and its vertical movement is controlled by the player. If the screen is tapped, the bird rises by a certain height $x$, and multiple taps within one unit time can stack the effects. If the screen is not tapped, the bird descends by a certain height $y$. The rise height $x$ and the descent height $y$ may differ at different horizontal positions.

The game fails if the bird's height is $0$ or if it hits a pipe. The bird cannot rise further if its height is $m$.

Now, please determine if the game can be completed. If it can, output the minimum number of screen taps required; otherwise, output the maximum number of pipe gaps the bird can pass through.

Input Format

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

The next $n$ lines, each containing two integers $x$ and $y$ separated by a space, sequentially represent the rise height $x$ and the descent height $y$ of the bird at the next position after tapping the screen or not tapping the screen at horizontal positions $0 \sim n-1$.

The next $k$ lines, each containing three integers $p, l, h$ separated by spaces, represent a pipe, where $p$ is the horizontal coordinate of the pipe, $l$ is the lower edge height of the pipe gap, and $h$ is the upper edge height of the pipe gap (the input data guarantees that $p$ is unique, but not necessarily in order).

Output Format

Two lines in total.

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

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.

Sample Input and Output

Input Sample #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 Sample #1

1
6

Input Sample #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 Sample #2

0
3

Notes

[Input and Output Sample Explanation]

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

[Data Range]

For $30\%$ of the data: $5 \leq n \leq 10, 5 \leq m \leq 10, k=0$, guaranteeing an optimal solution with a maximum of 3 taps per unit time.

For $50\%$ of the data: $5 \leq n \leq 20, 5 \leq m \leq 10$, guaranteeing an optimal solution with a maximum of 3 taps per unit 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,y < m$, $0 < p < n$, $0 \leq l < h \leq m$, $l + 1 < h$.

见题面 Input 部分

见题面 Output 部分