Lounge Lizards

Time limit5sMemory limit512 MB

Summary

Given a TV point and N lizards with positions and heights, find the largest subset where each lizard is strictly taller than every lizard on its segment to the TV.

Level: Medium7 of 10
Topics: Geometry, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

Monitor lizards are reptiles known for two things: cold blood and an addiction to computer screens. Their name says it, and they act on it, spending most of the day indoors in front of a small television in the lounge.

One reptile house now has a problem. So many lizards have gathered that not all of them can see the screen. A lizard sees the screen only if it is strictly taller than every lizard sitting on the straight segment between its own spot and the television.

The lizards do not care what is on the screen, and they do not care whether they watch it from an angle or head on. They only want the screen in view.

They also refuse to move. You can chase a lizard out of the room so that the ones behind it can see, or you can leave it where it sits, but no lizard accepts another spot in the room.

Chase lizards away optimally. How many lizards can stay and watch the screen at the same time?

Input

The first line contains two space-separated integers $TX$ and $TY$ ( $-10^6 \le TX, TY \le 10^6$ ), the coordinates of the television.
The second line contains one integer $N$ ( $1 \le N \le 10^6$ ), the number of lizards.
Each of the next $N$ lines contains three space-separated integers $X_i$ , $Y_i$ and $H_i$ ( $-10^6 \le X_i, Y_i \le 10^6$ , $1 \le H_i \le 10^6$ ), the coordinates and the height of one lizard.

The coordinates of the television and of the $N$ lizards are all distinct.

Output

Print the largest number of lizards that can stay and watch the television at the same time.

Examples3

Example 1
Input
```
50 50
2
60 50 1
65 50 2
```
Expected output
```
2
```
Example 2
Input
```
50 50
3
60 55 1
70 60 1
40 45 1
```
Expected output
```
2
```

Example 3

Input

Expected output