Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Limak and Shooting Points

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBearland is a dangerous place. Limak can’t travel on foot. Instead, he has *k* magic teleportation stones. Each stone can be used at most once. The *i*-th stone allows to teleport to a point (*ax*_{i}, *ay*_{i}). Limak can use stones in any order.

There are *n* monsters in Bearland. The *i*-th of them stands at (*mx*_{i}, *my*_{i}).

The given *k* + *n* points are pairwise distinct.

After each teleportation, Limak can shoot an arrow in some direction. An arrow will hit the first monster in the chosen direction. Then, both an arrow and a monster disappear. It’s dangerous to stay in one place for long, so Limak can shoot only one arrow from one place.

A monster should be afraid if it’s possible that Limak will hit it. How many monsters should be afraid of Limak?

Input

The first line of the input contains two integers *k* and *n* (1 ≤ *k* ≤ 7, 1 ≤ *n* ≤ 1000) — the number of stones and the number of monsters.

The *i*-th of following *k* lines contains two integers *ax*_{i} and *ay*_{i} ( - 10^{9} ≤ *ax*_{i}, *ay*_{i} ≤ 10^{9}) — coordinates to which Limak can teleport using the *i*-th stone.

The *i*-th of last *n* lines contains two integers *mx*_{i} and *my*_{i} ( - 10^{9} ≤ *mx*_{i}, *my*_{i} ≤ 10^{9}) — coordinates of the *i*-th monster.

The given *k* + *n* points are pairwise distinct.

Output

Print the number of monsters which should be afraid of Limak.

Examples

Input

2 4

-2 -1

4 5

4 2

2 1

4 -1

1 -1

Output

3

Input

3 8

10 20

0 0

20 40

300 600

30 60

170 340

50 100

28 56

90 180

-4 -8

-1 -2

Output

5

Note

In the first sample, there are two stones and four monsters. Stones allow to teleport to points ( - 2, - 1) and (4, 5), marked blue in the drawing below. Monsters are at (4, 2), (2, 1), (4, - 1) and (1, - 1), marked red. A monster at (4, - 1) shouldn't be afraid because it's impossible that Limak will hit it with an arrow. Other three monsters can be hit and thus the answer is 3.

In the second sample, five monsters should be afraid. Safe monsters are those at (300, 600), (170, 340) and (90, 180).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:38:01 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|