Alexander decided to build a swimming pool near his house and asked a team of designers to prepare a design.
The designers proposed a pool in the shape of a convex polygon with vertices at points $$$P_1, P_2, \ldots, P_n$$$. Vertex $$$P_i$$$ has coordinates $$$(x_i, y_i)$$$. The vertices are listed in counterclockwise order; no three vertices lie on the same line. It is known that $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$, all $$$y_i \le 0$$$, and $$$y_1 = y_n = 0$$$.
After estimating the cost of the work, Alexander decided to simplify the project: the new pool must have the shape of a convex polygon with exactly $$$k$$$ vertices. However, the workers have already marked out the site and even started digging, so the location of the pool cannot be chosen arbitrarily. The pool must have the shape of a convex polygon and completely contain the polygon in which the pool was originally planned to be placed. Each side of the pool must lie on one of the lines containing sides of the original polygon. Different sides of the new pool must use different lines. In addition, construction of the wall along side $$$P_1P_2$$$ has already begun, so one side of the new pool must lie on the line passing through vertices $$$P_1$$$ and $$$P_2$$$.
At the same time, Alexander's plot is not very large, so he wants to build a pool of minimum area satisfying these conditions.
The figures below show optimal designs for the new pool for the two examples from the statement. The shaded region denotes the new pool, and the dashed lines — extensions of the sides of the original polygon.
Help him find the minimum possible area of the new pool satisfying all the requirements.
The first line contains two integers $$$n$$$ and $$$k$$$ — the number of vertices of the original polygon and the required number of vertices of the new pool ($$$3 \le k \le n \le 10^5$$$).
Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of vertex $$$P_i$$$ ($$$-10^9 \le x_i \le 10^9$$$, $$$-10^9 \le y_i \le 0$$$).
It is guaranteed that the points are vertices of a convex polygon and are listed in counterclockwise order. No three vertices of the polygon lie on the same line. It is also guaranteed that $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$ and $$$y_1 = y_n = 0$$$.
Print one number — the minimum possible area of the new pool satisfying all the requirements.
The answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
4 3 0 0 1 -1 2 -1 3 0
2.25
4 4 0 0 1 -1 2 -1 3 0
2
In the first example, the new pool must have exactly three sides. The optimal solution is triangle $$$AED$$$. Its sides lie on the lines containing sides $$$AB$$$, $$$CD$$$, and $$$AD$$$ of the original polygon. The area of this triangle is $$$2.25$$$. The resulting pool is shown in the left figure.
In the second example, the new pool must have exactly four sides, so the original polygon can be left unchanged. Its area is $$$2$$$. The resulting pool is shown in the right figure.
| Name |
|---|


