H. Heaviest Convex Set
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A convex polygon is a simple polygon whose interior forms a convex set. Specifically, if any side of the polygon is extended indefinitely in both directions to form a straight line, all other sides lie entirely on the same side of this line. All interior angles of a convex polygon are less than $$$180^\circ$$$, and the line segment between any two vertices lies inside the polygon or on its boundary. A valid convex polygon must contain at least three vertices, and no three vertices are collinear.

Colin has $$$n$$$ points on a plane, the $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$ and a weight $$$w_i$$$.

Now Colin wants you to delete at most $$$k$$$ points so that the remaining points form exactly the vertex set of a convex polygon; under this condition, you need to maximize the sum of the weights of the remaining points.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(3 \le n \le 5\times 10^4$$$, $$$0 \le k \le 20$$$, $$$n-k \ge 3)$$$, representing the number of points and the maximum number of points that can be deleted.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$w_i$$$ $$$(1 \le x_i, y_i \le 10^9$$$, $$$|w_i| \le 10^9)$$$, describing the coordinates and weight of each point.

It is guaranteed that all coordinates are distinct.

Output

Output a single line containing an integer: the maximum possible sum of weights of the remaining points after deleting at most $$$k$$$ points, such that they form exactly the vertex set of a convex polygon.

If no valid solution exists, output "impossible".

Examples
Input
4 1
1 1 5
10 1 8
10 10 -16
1 10 3
Output
16
Input
9 6
1 1 1
1 2 1
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
Output
6
Input
5 0
1 1 1
1 3 1
3 1 1
3 3 1
2 2 1
Output
impossible