终于，这一天还是来了——三角形入侵了 Byteotia！Byteotia 坐落在一个岛屿上，占据了其整个表面。该岛屿的形状是一个凸多边形（即每个内角都小于 $180^\circ$ 的多边形）。Byteotia 上分布着一定数量的软件工厂，每一家工厂都会产生固定的收益或亏损。

三角形决定占领 Byteotia 的一部分区域，该区域需要满足：

• 是一个三角形区域，其三个顶点是该多边形岛屿的三个不同顶点，
• 能够带来最大的收益，即位于该占领区域内的所有工厂产生的收益与亏损之和最大。

我们假设位于占领区域边界上或顶点处的工厂属于该区域。不包含任何工厂的区域，其收益显然为零。

Byteotia 的国王 Byteasar 对三角形入侵可能造成的损失感到担忧。请你编写一个程序，计算三角形想要占领的区域内工厂所产生的收益与亏损之和。

你的程序需要：

• 从输入文件中读取 Byteotia 的形状描述以及工厂的位置，
• 确定以多边形岛屿的三个不同顶点为顶点的三角形内，所有工厂产生的收益与亏损之和的最大值，
• 将结果写入输出文件。

输入格式

输入文件的第一行包含一个整数 $n$ ($3 \le n \le 600$)，表示多边形岛屿的顶点数。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10\,000 \le x_i, y_i \le 10\,000$)，以空格分隔，按顺时针顺序表示岛屿连续顶点的 $x$ 和 $y$ 坐标。第 $n+2$ 行包含一个整数 $m$ ($1 \le m \le 10\,000$)，表示工厂的总数。在接下来的 $m$ 行中，每行包含三个整数 $x'_i$、$y'_i$ 和 $w_i$ ($-10\,000 \le x'_i, y'_i \le 10\,000$, $-100\,000 \le w_i \le 100\,000$)，以空格分隔，分别表示：第 $i$ 个工厂的 $x$ 和 $y$ 坐标，以及该工厂产生的收益（当 $w_i \ge 0$ 时）或亏损（当 $w_i < 0$ 时）。每家工厂都位于多边形岛屿内，即在岛屿内部或边界上。不同的工厂可能位于同一位置，即具有相同的坐标。

输出格式

输出文件的第一行也是唯一一行，应包含一个整数，表示以多边形岛屿的三个不同顶点为顶点的三角形内，所有工厂产生的收益与亏损之和的最大值。注意，结果可能是一个负整数。

样例

输入 1

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

输出 1

5