Maximum Delivery Requests

You are given a grid of size \(n \times n\) and \(m\) (which is equal to \(n\) in practice) along with a set of \(q\) delivery requests. Each request is described by five integers \(x_1, y_1, x_2, y_2, t\) representing the starting point \((x_1,y_1)\), the destination \((x_2,y_2)\), and the maximum allowed delivery time \(t\). A delivery can be performed if the shortest path (using Manhattan moves: up, down, left, and right) from the start to the destination is less than or equal to \(t\). Your task is to determine the maximum number of delivery requests that can be satisfied if the requests are scheduled greedily based on their allowed delivery time and actual travel time.

The shortest path length between two points \((x_1,y_1)\) and \((x_2,y_2)\) is given by the formula:

[ \text{distance} = |x_1 - x_2| + |y_1 - y_2| ]

Note: Although the problem statement provides two parameters \(n\) and \(m\), the grid boundaries are determined by \(n\) (i.e. the grid is \(n \times n\)).

inputFormat

The input is given via standard input (stdin) with the following format:

 n m
 q
 x1 y1 x2 y2 t
 x1 y1 x2 y2 t
 ... (q lines in total)

Here:

• \(n\) and \(m\) are integers representing the grid dimensions.
• \(q\) is the number of delivery requests.
• Each of the next \(q\) lines provides five integers representing a delivery request.
</p>

outputFormat

The output is a single integer printed to standard output (stdout) representing the maximum number of delivery requests that can be satisfied.

## sample

3 3
3
1 1 2 2 2
2 2 3 3 2
1 1 3 3 4

2

</p>