[AdditionalFile5501.zip](file://AdditionalFile5501.zip?type=additional_file)

#5501. 「POI2006 R2」入侵 The Invasion

标签: 传统 | 时间限制: 6000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Najazd

大事不好了——三角人入侵了字节国！字节国坐落于一座岛屿之上，并占据了其全部陆地。这座岛屿的形状是一个凸多边形（即每个内角都小于 $180^{\circ}$ 的多边形）。字节国境内有若干家软件工厂，每家工厂都会产生固定的盈利或亏损。

三角人决定占领字节国的一部分领土，这片领土需满足以下条件：

• 其形状为一个三角形，且其顶点为岛屿多边形的某三个不同的顶点，
• 能为他们带来最大的收益，即位于被占领土内的所有工厂的盈利与亏损之和应尽可能大。

我们约定，如果一家工厂位于被占领土的边界或顶点上，则它属于该领土。不包含任何工厂的领土显然收益为 $0$。

字节国国王 Bajtazar 正在思考，三角人的入侵可能会给国家经济带来多大的损失。请帮助他编写一个程序，计算出三角人意图占领的区域内，所有工厂的盈利与亏损总和。

请编写一个程序，实现以下功能：

• 从标准输入读取字节国（岛屿）的形状描述和工厂的位置信息，
• 找出一个以岛屿多边形的某三个不同顶点为顶点的三角形，使其内部（含边界）所有工厂的盈利与亏损之和达到最大值，
• 将该最大值输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$ $(3 \le n \le 600)$，表示岛屿多边形的顶点数量。

接下来的 $n$ 行，每行包含两个整数 $x_j$ 和 $y_j$ $(-10000 \le x_j, y_j \le 10000)$，由单个空格隔开，表示岛屿连续顶点的 $x$ 和 $y$ 坐标，按顺时针顺序给出。

第 $n+2$ 行包含一个整数 $m$ $(1 \le m \le 10000)$，表示工厂的数量。

接下来的 $m$ 行，每行包含三个整数 $x'_i, y'_i$ 和 $w_i$ $(-10000 \le x'_i, y'_i \le 10000, -100000 \le w_i \le 100000)$，由单个空格隔开，分别表示：第 $i$ 家工厂的 $x$ 和 $y$ 坐标，以及该工厂带来的盈利（当 $w_i \ge 0$ 时）或亏损（当 $w_i < 0$ 时）。每家工厂都位于岛屿多边形之内或其边界上。多家工厂可能位于同一位置，即坐标相同。

输出格式

输出的第一行且仅一行应包含一个整数，表示以岛屿多边形的某三个不同顶点为顶点的三角形区域内，所能包含的工厂盈利与亏损的最大总和。这个数值可能是负数。

样例

输入

5
4 1
1 4
8 9
11 5
8 1
4
7 2 3
6 3 -1
4 5 3
9 6 -4

输出

5