题目描述

Gil'ead 的指挥官 Arya 新招募了 $2n$ 名士兵。为了增加巡逻力量，她准备将这些新兵划分为 $n$ 对。

在现代战斗中，一支高效的双人巡逻队应由：

• 一名持盾者；
• 一名持矛者。

第 $i$ 名新兵具有：

• 持盾防御能力 $d_i$；
• 持矛攻击能力 $a_i$；
• 家乡城市 $c_i$。

一对新兵中，可以任选其中一人担任持盾者，另一人担任持矛者。

若持盾者为 $i$、持矛者为 $j$，则这一对的战斗力为：

如果两人来自同一座城市 $c$，还会额外获得 $c$ 点协同加成，即战斗力为：

请将全部 $2n$ 名新兵两两配对，并为每一对分配持盾者和持矛者，使所有巡逻队的战斗力之和最大。

输入格式

第一行包含一个整数 $n$（$1\le n\le 10^5$），表示新兵总数的一半。

接下来 $2n$ 行，第 $i$ 行包含三个整数 $d_i,a_i,c_i$（$1\le d_i,a_i,c_i\le 10^6$），分别表示第 $i$ 名新兵的持盾防御能力、持矛攻击能力和家乡城市编号。

输出格式

输出一个整数，表示所有配对方案中能够获得的最大总战斗力。

样例 1

输入

1
4 2 1
3 2 2

输出

6

说明

只有两名新兵，因此必须配成一对。令新兵 $1$ 持盾、新兵 $2$ 持矛。由于两人来自不同城市，不获得协同加成，总战斗力为 $4+2=6$。

样例 2

输入

2
1 2 5
4 2 5
5 1 5
3 2 1

输出

18

说明

一种最优方案为：

• 新兵 $3$ 持盾，与新兵 $1$ 持矛配对。两人都来自城市 $5$，战斗力为 $5+2+5=12$；
• 新兵 $2$ 持盾，与新兵 $4$ 持矛配对，战斗力为 $4+2=6$。

总战斗力为 $18$。

样例 3

输入

2
1 7 2
1 5 2
8 1 6
7 1 6

输出

27

说明

一种可行的最优配对为：新兵 $3$ 持盾与新兵 $1$ 持矛配对，新兵 $4$ 持盾与新兵 $2$ 持矛配对。