The Invasion

The Triangles have invaded Byteotia. Byteotia lies on an island and covers its entire surface, and the island has the shape of a convex polygon (every interior angle is smaller than $180^\circ$). Several software factories stand on the island, and each one produces a fixed gain or a fixed loss.

The Triangles want to seize a part of Byteotia that is:

• a triangular region whose three corners are three different vertices of the island polygon, and
• as profitable as possible, meaning the sum of the gains and losses of all factories inside the region is as large as it can be.

A factory that lies on the border of the seized region, or exactly at one of its corners, counts as belonging to that region. A region that holds no factory yields an income of $0$.

Byteasar, the King of Byteotia, wants to know how much the invasion could cost him. Write a program that reads the shape of the island and the positions of the factories, then reports the largest possible total of gains and losses of the factories captured by a triangle whose three corners are three different vertices of the island.

The first line contains a single integer $n$ ($3 \le n \le 600$), the number of vertices of the island polygon.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10000 \le x_i, y_i \le 10000$) separated by a single space, the coordinates of the polygon vertices given in clockwise order.

The next line contains a single integer $m$ ($1 \le m \le 10000$), the number of factories.

Each of the next $m$ lines contains three integers $x'_i$, $y'_i$ and $w_i$ ($-10000 \le x'_i, y'_i \le 10000$, $-100000 \le w_i \le 100000$) separated by single spaces: the coordinates of the $i$-th factory and the value it produces, which is a gain when $w_i \ge 0$ and a loss when $w_i < 0$. Every factory lies inside the island or on its border. Different factories may share the same coordinates.

Print a single integer: the largest possible sum of the gains and losses of the factories that lie inside a triangle whose three corners are three different vertices of the island polygon. The value may be negative.