Problem: The university of A stages a programming contest this year as has been the case in the past. As a member of the team in charge of devising the problems, you have worked out a set of input data for a problem, which is an arrangement of points on a 2D plane in the coordinate system. The problem requires that any combination of these points greater than or equal to $K$ in number must not align on a line. You want to confirm that your data satisfies this requirement.

Given the number of points $K$ and their respective 2D coordinates, make a program to check if any combination of points greater or equal to $K$ align on a line.



Input

The input is given in the following format.


$N$ $K$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_N$ $y_N$


The first line provides the number of points $N$ ($3 \leq N \leq 3000$) on the 2D coordinate system and an integer $K$ ($3 \leq K \leq N$). Each of the subsequent lines provides the $i$-th coordinate $x_i,y_i$ ($0 \leq x_i,y_i \leq 10000$) as integers. None of these coordinates coincide, i.e., if $i \ne j$, then $x_i \ne x_j$ or $y_i \ne y_j$.

Output

Output 1 if any combination of points greater or equal to $K$ aligns on a line, or 0 otherwise.

Examples

Input

5 4
0 0
1 0
1 1
0 1
2 2


Output

0


Input

7 5
0 0
1 0
1 1
0 1
2 0
3 0
4 0


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define ROOP() while (true)

int gcd(int a, int b){
	if(a == 0 || b == 0) return 1;
	int r;
    while ((r=a%b)){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    
	int N,K;
	cin >> N >> K;
	int x[3000],y[3000];
	for(int i=0; i<N; i++){
		cin >> x[i] >> y[i];
	}
	
	for(int i=0; i<N; i++){
        map<pair<int,int> ,int> tmp;
		for(int j=i+1; j<N; j++){
			int x2 = x[j]-x[i];
			int y2 = y[j]-y[i];
            int x3,y3;
            if(x2 >= 0) x3 = 1;
            else x3 = -1;
            if(y2 >= 0) y3 = 1;
            else y3 = -1;
            
            x2 = abs(x2);
            y2 = abs(y2);
			int g = gcd(x2,y2);
			x2 = x2 / g * x3;
			y2 = y2 / g * y3;
			if(x2 == 0) y2 = 1;
			if(y2 == 0) x2 = 1;

            if(tmp.count(make_pair(x2,y2)) == 0) tmp[make_pair(x2,y2)] = 1;
			tmp[make_pair(x2,y2)]++;
			if(tmp[make_pair(x2,y2)] >= K){
				cout << 1 << endl;
				return 0;
			}
		}
	}
	cout << 0 << endl;
    
    return 0;
}