CF1517G.Starry Night Camping

At the foot of Liyushan Mountain, $n$ tents will be carefully arranged to provide accommodation for those who are willing to experience the joy of approaching nature, the tranquility of the night, and the bright starry sky.

The $i$-th tent is located at the point of $(x_i, y_i)$ and has a weight of $w_i$. A tent is important if and only if both $x_i$ and $y_i$ are even. You need to remove some tents such that for each remaining important tent $(x, y)$, there do not exist $3$ other tents $(x'_1, y'_1)$, $(x'_2, y'_2)$ and $(x'_3, y'_3)$ such that both conditions are true:

1. $|x'_j-x|, |y'_j - y|\leq 1$ for all $j \in {1, 2, 3}$, and
2. these four tents form a parallelogram (or a rectangle) and one of its sides is parallel to the $x$-axis.

Please maximize the sum of the weights of the tents that are not removed. Print the maximum value.

在李雨山山脚下，将精心布置 $n$ 顶帐篷，为那些渴望亲近自然、感受夜晚宁静与璀璨星空的人们提供住宿。

第 $i$ 顶帐篷位于坐标 $(x_i, y_i)$ 处，权重为 $w_i$。当且仅当 $x_i$ 和 $y_i$ 均为偶数时，该帐篷被称为“重要帐篷”。你需要移除若干顶帐篷，使得对每一个剩余的重要帐篷 $(x, y)$，都不存在另外三顶帐篷 $(x'_1, y'_1)$、$(x'_2, y'_2)$ 和 $(x'_3, y'_3)$ 同时满足以下两个条件：

1. 对所有 $j \in \{1, 2, 3\}$，均有 $|x'_j - x| \leq 1$ 且 $|y'_j - y| \leq 1$；
2. 这四顶帐篷构成一个平行四边形（或矩形），且其一条边与 $x$-轴平行。

请最大化未被移除帐篷的权重之和，并输出该最大值。

The first line contains a single integer $n$ ($1\leq n\leq 1\,000$), representing the number of tents.

Each of the next $n$ lines contains three integers $x_i$, $y_i$ and $w_i$ ($-10^9\leq x_i,y_i \leq 10^9$, $1\leq w_i\leq 10^9$), representing the coordinate of the $i$-th tent and its weight. No two tents are located at the same point.

第一行包含一个整数 $n$（$1\leq n\leq 1\,000$），表示帐篷的数量。

接下来的 $n$ 行中，每行包含三个整数 $x_i$、$y_i$ 和 $w_i$（$-10^9\leq x_i,y_i \leq 10^9$，$1\leq w_i\leq 10^9$），分别表示第 $i$ 个帐篷的坐标及其重量。任意两个帐篷均不位于同一点。

A single integer — the maximum sum of the weights of the remaining tents.

一个整数——剩余帐篷的重量之和的最大值。

Here is an illustration of the second example. Black triangles indicate the important tents. This example also indicates all $8$ forbidden patterns.

以下是第二个示例的图示。黑色三角形表示重要的帐篷。该示例还标出了全部 $8$ 种禁止出现的模式。