Floating Points

Time limit1sMemory limit512 MB

Summary

Given a simple polygon ship and x-coordinates where balls are released far below it, count the balls that get trapped under the hull and push it up.

Level: Medium6 of 10
Topics: Geometry, Simulation
Solved: No attempts yet

Problem

Your ship has sunk. You want it back.

The best way to salvage a shipwreck is to release a whole bunch of ping pong balls beneath it. The balls float up to the surface, and their buoyancy takes the sunken ship up with them. They do that only while they actually push the ship up. If they slide off the shipwreck, float past it, or surface in an air bubble inside the ship, they do not contribute to lifting it out of the water.

You have already released a bunch of balls beneath your ship. Count how many of them actually help the salvage. You know exactly where each ball was released, and you have a precise model of the ship.

Figure 2: The shipwreck in this figure. The fourth ball from the left gets stuck between the anchor and the ship, so it helps.

The sea is the (x, y)-plane. The surface is at $y = 0$ , and the water is where $y \le 0$ . The shipwreck is a 2D polygon in this plane. The balls are points (floating point numbers) released far below the shipwreck.

A ball floats straight up unless it surfaces or an edge blocks it. If it can float up along an edge, it follows that edge. If a horizontal edge blocks it, or a corner with no edge going up from it blocks it, the ball is stuck.

A ball that surfaces does not push the ship up. A ball trapped below the ship at $y = 0$ still pushes the ship up and is counted.

Note: This does not work. Do not try this on your own sunken ship.

Input

The first line has two integers $n$ and $b$ , where $3 \le n \le 10^3$ is the number of vertices of the shipwreck and $1 \le b \le 2 \cdot 10^3$ is the number of balls.

The next $n$ lines each contain two integers $x$ and $y$ with $-10^5 \le x, y \le 10^5$ , the vertices of the polygon in counter-clockwise order.

The last line contains $b$ integers $x_1, x_2, \ldots, x_b$ with $|x_i| \le 10^5$ , the x-coordinates where the balls were released. The original y-coordinate of each ball is below $-10^5$ .

The shipwreck is a simple polygon: its edges only intersect at shared vertices, and only two edges meet at each vertex. No two x-coordinates are the same, whether they belong to the vertices of the ship or to the balls.

Output

Print one integer: the number of balls that push the shipwreck up.

Examples2

Example 1
Input
```
4 4
1 2
4 -4
6 0
9 0
2 3 5 8
```
Expected output
```
2
```

Example 2

Input

17 5
-28 2
-15 -5
-16 -4
2 -5
18 -1
21 -7
16 -7
22 -9
24 -8
26 -2
23 -6
20 0
28 2
0 2
1 15
-1 15
-2 2
-20 -10 10 19 25

Expected output