J. Junior Joining
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Patrol pair with shield and spear. Public Domain on publicdomainvectors (edited).

Arya, the Commander of Gil'ead, has received $$$2 \cdot n$$$ new recruits. Since the Gil'ead City Protectorate Council has mandated more patrols, she intends to pair them into $$$n$$$ pairs to patrol the area. To maximize the effectiveness of a patrol pair in the modern era, it should consist of one shield bearer and one spear carrier.

Each recruit $$$i$$$ has shield-defense skill $$$d_i$$$, and spear-attack skill $$$a_i$$$. While skilled usage of their respective tool is important, one should never neglect the effectiveness of strong synergy. Because of long-standing rivalries between cities, strong bonds have formed within each city. With enough discipline, Arya is sure that there will not be any bad blood within a pair, but if both are from the same city, they will synergize exceptionally well.

The total fighting strength of a pair is the sum of the shield-defense skill of one, the spear-attack skill of the other, and if both recruits are from the same city $$$c$$$, also a synergy bonus of $$$c$$$.

Determine the maximum sum of fighting strength over all pairs that Arya can achieve with optimal pairing.

Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$1\leq n \leq 10^5$$$), half the number of new recruits.
  • $$$2 \cdot n$$$ lines, the $$$i$$$th of which contains three integers $$$d_i$$$, $$$a_i$$$, and $$$c_i$$$ ($$$1 \leq d_i, a_i, c_i \leq 10^6$$$), the shield-defense skill, spear-attack skill, and the home city of the $$$i$$$th recruit.
Output

Output the maximum achievable sum of fighting strength over all pairs.

Examples
Input
1
4 2 1
3 2 2
Output
6
Input
2
1 2 5
4 2 5
5 1 5
3 2 1
Output
18
Input
2
1 7 2
1 5 2
8 1 6
7 1 6
Output
27
Note

In the first sample, there are only two recruits so they are paired together. Recruit $$$1$$$ is assigned the shield, recruit $$$2$$$ the spear. As they are not from the same city, only their skill is counted $$$4 + 2 = 6$$$.

In the second sample, recruit $$$3$$$ (shield) is paired with recruit $$$1$$$ (spear). As they are both from city $$$5$$$, they have $$$5$$$ bonus strength from synergy ($$$5 + 2 + 5 = 12$$$ total). Recruit $$$2$$$ (shield) and recruit $$$4$$$ (spear) are paired, resulting in a fighting strength of $$$6$$$.

In the third sample, one possible pairing is the following: recruit $$$3$$$ (shield) with $$$1$$$ (spear), and recruit $$$4$$$ (shield) with $$$2$$$ (spear).