Problem B
Greedy Cows

Photo by Iain McDonald

To split the pasture, he will select a number of points on the surrounding fence, and set up yet more fences between all pairs of selected points, except the points that lie on the same side of the surrounding fence. These new fences may cross. Now, this will create a number of mini-pastures in the pasture (see Figure 1).

MacDonald wants to minimize the number of points selected (not the total fence length, as you might have thought). How many points does he need to select in order to have at least one mini-pasture for each cow? Some of these mini-pastures might be tiny: that doesn’t bother Old MacDonald, but only mini-pastures with positive area count.

Figure 1: A possible solution to the first sample case below.

Input

The input begins with an integer $1 \le n \le 2^{60}$, the number of cows Old MacDonald has. Then follows an integer $3 \le F \le 100$ - the number of fence posts in Old MacDonald’s fence. The next $F$ lines will contain two integers $-10^9 \le C_ x,C_ y\le 10^9$, the coordinates of the posts. The $F$ fence posts form a convex polygon with positive area, given in clockwise order.

Output

Output an integer $p$, the minimum number of points Old MacDonald needs to select, so that each cow gets at least one mini-pasture each.

5
4
0 0
0 4
4 4
4 0

4

13
5
1 3
2 3
3 2
2 1
1 1

5