Closed-Circuit Surveillance

There is a building shaped like a convex n-gon. You want to install CCTV cameras outside the building so that every outer wall is monitored. Cameras may be installed only at the m given exterior locations.

Figure 1	Figure 2	Figure 3

Suppose the available installation locations are as shown in Figure 1. If a camera is installed at location 1, it can monitor the two walls marked in red in Figure 2. However, if the camera and a wall lie on the same straight line, that wall is not considered monitored. For example, if a camera is installed at location 6, it cannot monitor the wall marked in blue in Figure 3.

By installing cameras at several locations, it may be possible to monitor every outer wall. In the situation from Figure 1, installing cameras at locations 1, 2, 4, and 6 works as in Figure 4. Installing cameras at locations 1, 3, 5, and 7 also works, as shown in Figure 5.

Figure 4	Figure 5

Each available location has its own installation cost. Compute the minimum total cost needed to install cameras so that every outer wall is monitored.

The first line contains two natural numbers n and m, where 1 ≤ n ≤ 1,000 and 1 ≤ m ≤ 1,000.

Each of the next n lines contains the x and y coordinates of one polygon vertex, given in counterclockwise order. Each of the following m lines contains the x-coordinate, y-coordinate, and installation cost of one available camera location.

All numbers on a line are separated by spaces. Every coordinate is an integer whose absolute value does not exceed 100,000, and every installation cost is a natural number not exceeding 100,000. No two adjacent sides of the polygon lie on the same straight line.

Print the minimum cost required to install cameras so that every outer wall is monitored. If it is impossible, print -1.