On a certain day, while cleaning up the warehouse, Marisa found a map with the inscription: Go in search of treasure. The map describes in detail a land area in the shape of a convex polygon with $n$ vertices, and $m$ positions specifying the locations of $m$ treasures on that land. Each treasure has a certain value (this value can be negative).
Marisa is a person who loves solving geometric problems. Therefore, instead of going in search of treasure as in blockbuster adventure movies, Marisa sits in the warehouse, studying the map to select 3 distinct vertices out of the $n$ vertices of the land so that the total value of treasures within the triangle formed by those 3 vertices is as large as possible (if a treasure is on the edge of the triangle, it is also considered within the triangle) based on the information on the map.
Requirement: Write a program to find the desired solution for Marisa.
### Input
- The first line contains the number $n (3 ≤ n ≤ 600)$, which is the number of vertices of the outer polygon.
- The next $n$ lines, the $i$-th line contains two integers $(x_i, y_i)$, $|x_i|, |y_i| \le 10^5$, the coordinates of the $i$-th vertex of the polygon. The vertices are listed clockwise.
- The next line contains the integer $m (1 \le m \le 5 \times 10^4)$, which is the number of points.
- The next $m$ lines, the $i$-th line contains three integers $u_i, v_i, w_i$: at the point $(u_i, v_i)$ there is a treasure with a value of $w_i$ ($|u_i|, |v_i| \le 10^5, |w_i| \le 10^6)$. Treasure positions may overlap.
### Output
- Print the maximum value of treasure found.
### Constraints
- 30% of tests have $n \le 65; m \le 200$.
- 40% of tests have $n \le 600; m \le 10^4$.
- 30% of tests have $n \le 600; m \le 5 \times 10^4$.
### Example
Input:
```
6
1 1
4 0
6 1
7 5
4 6
0 4
5
4 5 2
3 4 3
1 2 -2
3 3 6
5 2 4
```
Output:
```
15
```
