Hay Removal for Tractor Routing

After a long day of work, farmer John suddenly realized that his tractor is still parked at its location in the center of the field. To make matters worse, his mischievous cows have dropped n piles of hay at various points on the field. The tractor and the hay piles are modeled as points on the 2D integer grid. Note that no hay pile is located at the tractor's starting position.

John needs to drive his tractor back to the origin (0,0) by moving only along the coordinate axes (i.e. in the north, south, east or west directions). In each move the tractor can travel an integer number of units in one of these directions. However, the tractor is not allowed to move onto any point that contains a hay pile.

In order to clear a path, John can remove some hay piles. Your task is to help him determine the minimum number of hay piles that must be removed so that there exists an axis‐parallel path from the tractor's starting position to the origin.

Formally, given the tractor's starting point \( (s_x,s_y) \) and a set \( S \) of n obstacle points (hay piles) with integer coordinates (none of them equal to \( (s_x,s_y) \)), determine the minimum number \( k \) such that if John removes \( k \) hay piles, there is a path from \( (s_x,s_y) \) to \( (0,0) \) moving in steps of unit distance in the four cardinal directions and never stepping onto an obstacle that has not been removed.

Note: All formulas are written in LaTeX format; for example, \( n \) denotes the number of hay piles and \( (0,0) \) denotes the coordinate origin.

inputFormat

The first line of input contains three space‐separated integers: \( s_x \), \( s_y \) and \( n \) (the number of hay piles).

Each of the following \( n \) lines contains two space‐separated integers \( x_i \) and \( y_i \) indicating the coordinates of a hay pile.

Constraints: It is guaranteed that none of the hay piles is located at \( (s_x,s_y) \).

outputFormat

Output a single integer: the minimum number of hay piles that need to be removed in order for the tractor to reach \( (0,0) \).

sample

1 0 1
0 0

1