题目描述

小 H 喜欢出最大权独立集问题。接下来，他还想了 $n$ 道最大权独立集问题。

在人类智慧的山巅，有一台字长为 $1048576$ 的计算机，小 H 把他出的 $n$ 道最大权独立集问题存储在这台计算机中，其中第 $i$ 道最大权独立集问题存储在芯片的第 $x$ 行第 $y$ 列的位置上，保证每道题所处的位置互不相同。

小 H 对于每道最大权独立集问题进行了难度评估，他认为第 $i$ 道题的难度值为 $a_i$，并且认为一道最大权独立集问题是重要的当且仅当它的在芯片中存储的位置的横纵坐标均为偶数。

由于计算机的内存分配漏洞，如果存在一道重要的题与三道和这道题在芯片中的存储位置的切比雪夫距离不超过 $1$ 的题目，并且它们在芯片中的位置构成了一个有一条边与 $x$ 轴平行的平行四边形，那么就会引发内存泄露，从而导致雪崩。

现在，为了避免雪崩的发生，小 H 只好忍痛割爱，删除一些最大权独立集问题，使得在避免雪崩的情况下留下总难度值之和最大的题目。

输入格式

第一行包含一个正整数 n，表示题目的数量。

接下来 n 行，每行包含三个整数 x_i y_i v_i，分别表示这道题目所在位置的横坐标、纵坐标和这道题的难度值（$v_i$）。

输出格式

输出一行一个非负整数，表示剩下的题目的最大难度总和。

样例 1 输入

5
0 0 4
0 1 5
1 0 3
1 1 1
-1 1 2

样例 1 输出

12

数据范围

对于所有测试数据，保证 $1\le n\le 2\times 10^4$，$-10^9\le x_i,y_i\le 10^9$，$1\le v_i\le 10^9$。

测试点说明（表格）：

| 测试点编号 | $n\le$ | $|x_i|,|y_i|\le$ | 特殊性质 | | ---------: | :------------: | :--------------: | :------: | | 1~2 | 5 | $10^9$ | | | 3~4 | 20 | $10^9$ | | | 5~7 | 100 | 10 | | | 8~10 | 1000 | $10^9$ | A | | 11~13 | 1000 | $10^9$ | B | | 14~16 | 1000 | $10^9$ | | | 17~20 | $10^4$ | $10^9$ | | | 21~25 | $2\times 10^4$ | $10^9$ | |

特殊性质说明：

• A：$v_i = 1$。
• B：对于每道重要的题目，$v_i = 10^9$；对于每道非重要的题目，$v_i \le 10^6$。