K-Convex Hull

Time limit1sMemory limit1024 MB

Summary

Given N distinct points, count how many single points can be removed so that the convex hull of the remaining points has exactly K vertices.

Level: Hard8 of 10
Topics: Geometry, Sorting, Divide and conquer
Solved: No attempts yet

Problem

Given $N$ distinct points on a 2D plane, remove one point. The convex hull of the remaining $N-1$ points must have exactly $K$ vertices. Write a program that counts the number of points that can be removed. If several points lie on an edge of the convex hull, only the two endpoints of that edge are counted as vertices.

Input

The first line contains $N$ and $K$ ( $4 \leq N \leq 500\,000$ , $3 \leq K \leq N-1$ ). The next $N$ lines each contain the $x$ and $y$ coordinates of a point, separated by a space. Every coordinate is an integer with absolute value at most $10^9$ , and all points are distinct.

Output

Print the number of points that can be removed.

Hint

If the remaining points lie on a single line after a point is removed, the convex hull has only two vertices, so that case is not counted.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
5 3
1 1
2 3
3 1
3 2
4 1
```
Expected output
```
4
```
Example 3
Input
```
5 4
1 1
2 3
3 1
3 2
4 1
```
Expected output
```
1
```

Example 4

Input

Expected output

Example 5

Input

Expected output