Maximal Triangle Factory Income

Byteotia is an island whose shape is a convex polygon. Inside (or on the boundary of) this island, there are several factories. Each factory has an integer weight representing gains (positive) or losses (negative). The Triangles are invading Byteotia and plan to seize a triangular area defined by three different vertices of the polygon such that the sum of weights of all factories located inside or on the border of this triangle is maximized.

More formally, let the convex polygon have n vertices and m factories. Each factory is represented by its coordinates and an associated weight. A factory is considered captured by a triangle if its position lies within or exactly on the edges (or vertices) of that triangle. Your task is to find a triangle formed by any three distinct vertices of the polygon that maximizes the total weight of the captured factories, and then output that maximal sum.

Note: Any formulas are given in LaTeX format. For example, the interior angles of the convex polygon are all less than \(180\degree\).

inputFormat

The first line contains two integers n and m, where \(3 \le n \le 600\) is the number of vertices of the convex polygon and \(0 \le m \le 10000\) is the number of factories.

The following n lines each contain two integers \(x_i\) and \(y_i\), giving the coordinates of the polygon's vertices in order (either clockwise or counter-clockwise).

The next m lines each contain three integers \(x\), \(y\) and \(w\) representing the coordinates of a factory and its weight.

outputFormat

Output a single integer representing the maximum sum of weights of factories that can be captured by an invading triangle (one whose vertices are chosen from the polygon vertices). If no factory is captured in a triangle, then its income is 0.

sample

3 3
0 0
5 0
0 5
1 1 10
2 1 -5
1 3 7

12