Galactic Warlords

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.

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 a single integer: the minimum number of lines you must add to the proposal so that all warlords can be satisfied.