Isabel's birthday party is about to end, and like at almost any party, it's time to eat cake. Isabel prepared a cake for her party in the shape of a convex polygon, which still needs candles. Isabel likes things to look orderly, so she only puts candles in positions on the cake that have integer coordinates. Isabel has decided to add candles only at integer coordinates on the cake that meet the following characteristics:
- The coordinate is inside the cake or on its boundary.
- The coordinate can be the endpoint of a line segment that touches at least $$$N$$$ points with integer coordinates inside the cake or on its boundary.
Given $$$P$$$ vertices of the polygon that form the cake, and $$$N$$$ (the number of points that the line segment must touch), what is the maximum number of candles Isabel can place on her cake?
In the picture above the birthday cake has $$$4$$$ vertices $$$(0,0)$$$, $$$(2,0)$$$, $$$(3,3)$$$, and $$$(3,6)$$$, if $$$N = 4$$$, then $$$7$$$ candles can be put on the cake. The coordinates where the candles are put are shown with an X.
The first line of input contains two integer numbers separated by a space $$$P$$$ ($$$3 \leq P \leq 1000$$$) and $$$N$$$ ($$$2 \leq N \leq 10^4$$$), representing the number of vertices of the polygon that form the cake and the minimum number of integer coordinates the segments must touch.
Each of the next $$$P$$$ lines contains two integer numbers separated by a space $$$x_i$$$, $$$y_i$$$, ($$$0 \leq x_i, y_i, \leq 5000$$$) representing the coordinates of the $$$i$$$-th vertex in the polygon.
Print a line with a single integer number, the number of candles that can be put on the cake following Isabel's conditions.
4 40 03 32 03 6
7
5 20 01 02 03 33 6
13
3 50 03 105 0
24
