Card Game Is Great Fun

Anna often played card games with her friend Bruno. She got bored of games for two players, so she invented a card game that one person can play alone.

At the start of the game, N cards of various colors are laid out in a row, and each card has one integer written on it. Each card's color is also an integer, and each card has a value. At the start, the card at position i (1 \le i \le N) from the front of the row has color $C_i$, written integer $A_i$, and value $V_i$.

The game repeats the following step. Anna removes one card from the row and adds it to the top of a draw pile. The pile starts empty.

• Step: Choose the 1st or the 3rd card from the front of the row. If the pile is not empty, you can only choose a card whose color or written integer matches at least one of the top card's color or written integer. Remove the chosen card from the row and place it on top of the pile.

The game ends when no card can be chosen. Anna's score is the total value of the cards in the pile at that point.

Write a program that finds the maximum score Anna can get.

Read the following data from standard input.

• The first line contains an integer $N$, the number of cards in the row at the start.
• Line $i$ of the following $N$ lines ($1 \le i \le N$) contains three integers $C_i$, $A_i$, $V_i$, separated by spaces. These mean that the card at position $i$ from the front has color $C_i$, written integer $A_i$, and value $V_i$.

Print the maximum score Anna can get as a single integer on one line to standard output.

• $1 \le N \le 500$
• $1 \le C_i \le 500$ ($1 \le i \le N$)
• $1 \le A_i \le 500$ ($1 \le i \le N$)
• $1 \le V_i \le 1000000$ ($1 \le i \le N$)