A convex polygon is a simple polygon whose interior forms a convex set. Specifically, a polygon is convex if, for any edge, extending it into a line in both directions results in all other edges of the polygon lying on the same side of that line. All interior angles of a convex polygon are not reflex angles, and the line segment connecting any two vertices lies entirely within or on the boundary of the polygon. A valid convex polygon must contain at least 3 vertices, and no three vertices can be collinear.

Given $n$ points on a plane, where the $i$-th point has coordinates $(x_i, y_i)$ and a weight $w_i$, write a program to remove at most $k$ points from these $n$ points such that the remaining points form the set of vertices of a convex polygon, and the sum of the weights of the remaining points is maximized.

Input

The first line contains two integers $n, k$ ($3 \le n \le 1000$, $0 \le k \le 10$, $n - k \ge 3$), representing the number of points and the maximum number of points that can be removed, respectively.

The next $n$ lines each contain three integers $x_i, y_i, w_i$ ($1 \le x_i, y_i \le 10^9$, $|w_i| \le 10^6$), describing the coordinates and weight of each point.

The input guarantees that all points have distinct coordinates.

Output

Output a single integer representing the maximum possible sum of the weights of the remaining points. If no valid solution exists, output impossible.

Examples

Input 1

4 1
1 1 5
10 1 8
10 10 -16
1 10 3

Output 1

16

Input 2

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 2

6

Input 3

5 0
1 1 1
1 3 1
3 1 1
3 3 1
2 2 1

Output 3

impossible