Minimum Total Waiting Time at Intersection

You are given a grid of size \( n \times n \) and \( m \) vehicles. Each vehicle has a starting coordinate and an ending coordinate, and it moves either horizontally or vertically. The path of a vehicle consists of every grid cell between its start and end positions (inclusive). When the paths of two or more vehicles overlap, they must wait to avoid collision, and for each grid cell where \( k \) vehicles overlap (with \( k \geq 2 \)), an extra waiting time of \( k-1 \) is added.

Your task is to compute the minimum total waiting time required to allow all vehicles to move without collisions.

Note: If a vehicle's coordinates are given as \( (x_1, y_1, x_2, y_2) \), it is guaranteed that either \( x_1 = x_2 \) (horizontal movement) or \( y_1 = y_2 \) (vertical movement).

The formula for additional waiting time at a grid cell is given by: \[ W = \sum_{\text{cell}} (k_{\text{cell}} - 1), \quad \text{for each cell with } k_{\text{cell}} \ge 2. \]

inputFormat

The input is given from stdin in the following format:

 n m
 x1 y1 x2 y2
 x1 y1 x2 y2
 ... (m lines total)

\( n \) is the size of the grid and \( m \) is the number of vehicles. Each of the next \( m \) lines contains four space-separated integers representing the starting and ending coordinates of a vehicle.

outputFormat

Output a single integer to stdout which is the minimum total waiting time required so that no two vehicles collide.

## sample

4 2
1 1 1 4
2 1 2 4

0

</p>