Captain Bajtazar is hunting "segment-creatures" on the planet Tumulum VI. His ship is stationed at the landing site (which we consider to be the origin of the coordinate system) and is equipped with a stun laser. The laser can be rotated so that the beam is directed at any angle. The ship's power supply is sufficient for at most $k$ shots, each of which can be fired at any chosen angle. Once the laser is turned on, it cannot be rotated.

There are $n$ segment-creatures on the planet—each is a one-dimensional being (a line segment) with endpoints at positive integer coordinates. Bajtazar's goal is to hit as many segment-creatures as possible with the laser beam, with the condition that no creature may be hit more than once—the captain wants to sell them for a good profit, and for that, they must be in perfect physical and mental condition. The laser beam travels along a straight line, and when it hits a segment, it passes through it and continues. If the laser beam passes through the very end of a segment or along the segment itself, it is also considered hit.

Write a program that determines the maximum number of segment-creatures that can be hit by the laser beam, according to the rules above.

Input

The first line of standard input contains two integers $k$ and $n$ ($1 \le k \le 100$, $1 \le n \le 500\,000$), separated by a single space. The following $n$ lines describe the segment-creatures, one per line. Each of these lines contains four positive integers $x_1, y_1, x_2, y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 1\,000\,000$), separated by single spaces. These numbers represent a segment-creature with endpoints $(x_1, y_1)$ and $(x_2, y_2)$.

In tests worth 36% of the points, the additional condition $k \le 2$ holds; in tests worth 45% of the points, $n \le 2\,000$ and $k \le 30$ hold; while in tests worth 81% of the points, $n \le 200\,000$ and $k \le 50$ hold.

Output

Your program should output, on the first (and only) line of standard output, exactly one integer: the maximum number of segment-creatures that can be hit by the laser beam (each exactly once), by performing at most $k$ shots.

Evaluation tests

• 1ocen: $k = 4, n = 5$, small correctness test;
• 2ocen: $k = 2, n = 5$, only zero-length segments;
• 3ocen: $k = 2, n = 3$, tricky correctness test;
• 4ocen: $k = 3, n = 500\,000$, maximum size test.

Examples

Input 1

3 6
1 2 2 4
3 1 5 1
3 2 2 3
3 3 3 4
2 2 2 2
6 1 3 5

Output 1

5

Note

Explanation for the example: It is sufficient to fire the laser twice. The laser beam is marked in the drawing with a dashed line.