Description

Flappy Bird is a once-popular casual mobile game. The player needs to continuously control the tapping frequency to adjust the bird’s altitude so that it passes through the gaps between the 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 modify the game rules as follows:

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

The bird always moves within the game interface. It starts from any integer height on the left edge of the interface, and the game is completed when it reaches the right edge.

In each unit of time, the bird moves a distance of $1$ to the right along the horizontal axis. Its vertical movement is controlled by the player. If the screen is tapped, the bird rises by a certain height $x$, and you may tap multiple times within one unit of time with the effects adding up; if you do not tap, the bird falls by a certain height $y$. The rise $x$ and fall $y$ can vary with the bird’s horizontal position.

If the bird’s height equals $0$ or it hits a pipe, the game fails. When the bird’s height is $m$, it cannot rise further.

Now, please determine whether the game can be completed. If it can, output the minimum number of taps. Otherwise, output the maximum number of pipe gaps the bird can pass through.

Input Format

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

The next $n$ lines each contain $2$ integers $x$ and $y$, separated by a single space. For horizontal positions $0 \sim n - 1$ in order, $x$ denotes how much the bird will rise at the next position if the player taps at this position, and $y$ denotes how much the bird will fall at the next position if the player does not tap at this position.

Then follow $k$ lines, each containing $3$ integers $p, l, h$, separated by single spaces. Each line describes one pipe, where $p$ is the pipe’s horizontal coordinate, $l$ is the lower boundary of the gap, and $h$ is the upper boundary of the gap (the input guarantees that all $p$ are distinct, but they are not guaranteed to be in sorted order).

Output Format

Output two lines.

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 taps required to complete the game. Otherwise, output the maximum number of pipe gaps the bird can pass through.

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 

1
6

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  

0
3

Hint

[Explanation for the sample input and output]

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

Constraints

• For $30\%$ of the testdata: $5 \leq n \leq 10$, $5 \leq m \leq 10$, $k = 0$, and there exists an optimal solution where at most $3$ taps occur within any single unit of time.
• For $50\%$ of the testdata: $5 \leq n \leq 20$, $5 \leq m \leq 10$, and there exists an optimal solution where at most $3$ taps occur within any single unit of time.
• For $70\%$ of the testdata: $5 \leq n \leq 1000$, $5 \leq m \leq 100$.
• For $100\%$ of the testdata: $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$.

Translated by ChatGPT 5