Lounge Lizards

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.

Medium7GeometrySortingGreedyImplementationNo attempts yetTime limit5sMemory limit512 MB

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 TXTX and TYTY (106TX,TY106-10^6 \le TX, TY \le 10^6), the coordinates of the television.
  • The second line contains one integer NN (1N1061 \le N \le 10^6), the number of lizards.
  • Each of the next NN lines contains three space-separated integers XiX_i, YiY_i and HiH_i (106Xi,Yi106-10^6 \le X_i, Y_i \le 10^6, 1Hi1061 \le H_i \le 10^6), the coordinates and the height of one lizard.

The coordinates of the television and of the NN lizards are all distinct.

Output

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