Galactic Warlords

Time limit1sMemory limit128 MB

Summary

Given N lines in the plane, find the minimum number of extra lines to add so that the arrangement has at least W unbounded regions (sectors of infinite area).

Level: Hard8 of 10
Topics: Geometry, Combinatorics, Math, Greedy
Solved: No attempts yet

Problem

Will the galaxy finally know peace? All the warlords have gathered to divide up space among themselves. The negotiations have come a long way, and the warlords have at last agreed on a peaceful way of deciding who gets what.

First, the 2-dimensional galactic map is divided into sectors by cutting it along a set of infinite straight lines. The warlord with the largest fleet chooses one sector, then the warlord with the second-largest fleet chooses another sector, and so on, until every warlord has taken a sector. This is then repeated until there are no sectors left.

Because no warlord will settle for less space than anyone else, there can be peace only if every warlord ends up with the exact same area. Since space is infinite, so is the map, and some sectors therefore have infinite area — that is exactly the amount of space everyone wants. You are allowed to add extra infinite lines to a proposed division. Determine the minimum number of extra lines you must add so that each of the $W$ warlords can take at least one sector of infinite area.

Input

The first line contains two positive integers $W$ and $N$ ( $1 \le W, N \le 100$ ): the number of warlords and the number of lines in the proposed division of space. Each of the next $N$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ (each with absolute value at most $10000$ ), describing a line that passes through the two distinct points $(x_1, y_1)$ and $(x_2, y_2)$ on the map.

Output

Output a single integer: the minimum number of lines you must add to the proposal so that all warlords can be satisfied.

Examples2

Example 1
Input
```
2 1
1 1 -2 0
```
Expected output
```
0
```
Example 2
Input
```
5 3
0 5 5 5
0 0 1 1
2 2 3 3
```
Expected output
```
1
```