鲤鱼山脚下,会精心布置$$$n$$$帐篷,为愿意体验亲近自然的愉悦、夜晚的宁静、璀璨星空的人们提供住宿。
第 $$$i$$$ 帐篷位于 $$$(x_i, y_i)$$$ 点,重量为 $$$w_i$$$。当且仅当 $$$x_i$$$ 和 $$$y_i$$$ 都是偶数时,帐篷才重要。您需要移除一些帐篷,以便对于每个剩余的重要帐篷 $$$(x, y)$$$,不存在 $$$3$$$ 其他帐篷 $$$(x'_1, y'_1)$$$、$$$(x'_2, y'_2)$$$ 和 $$$(x'_3, y'_3)$$$,这样两个条件都成立:
1. $$$|x'_j-x|, |y'_j - y|\leq 1$$$ 对于 \{1, 2, 3\}$$$ 中的所有 $$$j,并且
2. 这四个帐篷形成一个平行四边形(或矩形),其一条边平行于 $$$x$$$ 轴。
请最大化未拆除的帐篷的重量总和。打印最大值。
输入
第一行包含一个整数$$$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$$$ 个帐篷及其重量。没有两个帐篷位于同一地点。
输出
单个整数 — 剩余帐篷重量的最大总和。
示例
输入 #1
5 0 0 4 0 1 5 1 0 3 1 1 1 -1 1 2
输出 #1
12
输入 #2
32 2 2 1 2 3 1 3 2 1 3 3 1 2 6 1 2 5 1 3 6 1 3 5 1 2 8 1 2 9 1 1 8 1 1 9 1 2 12 1 2 11 1 1 12 1 1 11 1 6 2 1 7 2 1 6 3 1 5 3 1 6 6 1 7 6 1 5 5 1 6 5 1 6 8 1 5 8 1 6 9 1 7 9 1 6 12 1 5 12 1 6 11 1 7 11 1
输出 #2
24
注意
这是第二个示例的说明。黑色三角形表示重要的帐篷。此示例还指示所有 $$$8$$$ 禁止的模式。