Pineapple Pizza

Time limit1sMemory limit256 MB

Summary

Given n points and a center Q, decide whether k rays from Q can split the plane so every sector holds exactly n/k points, with no point on a ray.

Level: Hard8 of 10
Topics: Geometry, Sorting, Binary search, Two pointers
Solved: No attempts yet

Problem

There is a very large pineapple pizza. It is so large that it is treated as an infinite two-dimensional plane. The pizza has $n$ pineapple pieces, written as points $P_1, P_2, \dots, P_n$ . Each piece counts as a point with no area. A point $Q$ and a number $k$ of people are given. Draw $k$ rays that start at $Q$ and split the pizza into $k$ parts. Every part must hold the same number of pineapple pieces. No pineapple piece may lie on a border line. Write a program that decides whether such $k$ rays exist.

Input

The first line gives $n$ and $k$ ( $2 \le n, k \le 8000$ ). The next $n$ lines give the coordinates of the points $P$ . Line $i + 1$ gives the $x$ and $y$ coordinates of $P_i$ . Line $n + 2$ gives the $x$ and $y$ coordinates of $Q$ . All points $P$ and the point $Q$ are pairwise distinct. Every coordinate is an integer from $-10^5$ to $10^5$ .

Output

Print YES when such rays exist, and NO otherwise.

Hint

See the figure below.

Examples1

Example 1

Input

Expected output

YES