Electrical Outlets

For some episodes of the “GeOlymp Series”, the organizers run the contest from the home of one of the GeOlymp members.
Each organizer brings their own laptop and a power cable, and they all sit in a single room.

The problem arises when everyone tries to plug in their laptops. Each organizer has already chosen a fixed position in the room and does not want to move.
Some organizers may find that their power cable is not long enough to reach any socket, or that the available sockets cannot be assigned in a way that powers every laptop.

Fortunately:

Any power cable can be used with any laptop (so cables can be swapped).
However, one socket can only power one laptop at a time.

You are given:

The positions of the organizers in the room.
The length of each organizer’s power cable.
The positions of the wall sockets.

Find the minimum number of laptops that will remain without power if the cables and sockets are assigned optimally.

Room Setup

The room is a square with corners at coordinates:

$(0, 0)$
$(0, 500)$
$(500, 500)$
$(500, 0)$

All coordinates are given in centimeters.
All sockets are located on the walls (but not in the corners).

Input Format

The first line contains a single integer $T$ - the number of test cases.
Each testcase starts with a line containing two integers $N$ and $K$ — the number of organizers and the number of sockets.
The following line contains $N$ integers - the lengths of cables of each organizer.
The next $N$ lines describe the organizer positions:
Each line contains two integers $X_{i}$ , $Y_{i}$ — the position $(X_{i}, Y_{i})$ of the organizer $i$ .
The next $K$ lines describe the sockets:
Each line contains two integers $U_{j}$ , $V_{j}$ — the position $(U_{j}, V_{j})$ of socket $j$ .

Output Format

For each test case $i$ , output a single line "Case #i: num", where $n u m$ is the minimum number of laptops that will remain without power after the best possible assignment of cables to laptops and laptops to sockets.

Constraints

$1 \leq N, K \leq 9$
$0 < L_{i} < 1000$
$0 < X_{i}, Y_{i} < 500$
Each socket is located on one of the four walls but not at a corner.
All coordinates and lengths are integers.
No two organizers share the same position.
No two sockets share the same position.

Example

Input

2
3 3
1 3 3
1 1
1 2
1 3
0 1
3 0
2 0
4 4
10 10 10 10
250 10
250 490
10 250
490 250
250 0
500 250
250 500
0 250

Output

Case #1: 1
Case #2: 0

Explanation

Sample 1:

There is no assignment of outlets and power cables that lets every organizer have power.

sample1

Sample 2:

sample2