Siru's Walk

Time limit1sMemory limit1024 MB

Summary

Given pillars on a plane and circular smell zones from other dogs, count the most pillars Siru can mark with its own smell of radius R0.

Level: Medium5 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

Marking is the act of a dog marking its territory with urine.

Siru, a cute dog, walks on a two-dimensional plane. While walking, Siru marks the pillars it passes. Because Siru is afraid of other dogs, it does not mark a pillar where the smell of another dog's urine is present.

Specifically, there are $N$ pillars along the walking path, and other dogs have already made $M$ marks. The $i$ -th mark ( $1 \leq i \leq M$ ) is on pillar $P_i$ , and its smell spreads up to a distance of $R_i$ from that pillar.

Siru marks a pillar that has no smell of another dog, and its smell spreads up to a distance of $R_0$ from that pillar. If Siru's smell covers a pillar that had another dog's smell, Siru can mark that pillar.

Find the maximum number of pillars Siru can mark.

The distance between two pillars $(X_i, Y_i)$ and $(X_j, Y_j)$ is defined as $\sqrt{(X_i-X_j)^2 + (Y_i-Y_j)^2}$ .

Input

The first line contains $N$ and $M$ , separated by a space.

From line 2 to line $N+1$ , line $i+1$ contains the coordinates $X_i, Y_i$ of pillar $i$ , separated by a space.

Line $N+2$ contains $P_1, P_2, \cdots, P_M$ , separated by spaces.

Line $N+3$ contains $R_0, R_1, R_2, \cdots, R_M$ , separated by spaces.

Output

Print the number of pillars Siru can mark.

Constraints

$1 \leq N \leq 3\,000$
$1 \leq M \leq 3\,000$
$1 \leq P_i \leq N$
$1 \leq X_i,Y_i,R_i \leq 30\,000$ , and all $X_i$ , $Y_i$ , $R_i$ are integers

Examples1

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