Anna used to play card games with her friend Bruno, but she got bored of two-player games and decided to think of a card game that can be played by one person.

At the start of this game, $N$ cards of various colors are lined up in a row, and each card has one integer written on it. Each card's color is represented by an integer. Additionally, each card has a fixed value. At the start of the game, the color of the card at the $i$-th position ($1 \le i \le N$) from the front of the row is $C_i$, the integer written on it is $A_i$, and its value is $V_i$.

The game is played by repeatedly choosing one card from the row, removing it, and adding it to a stack. Initially, there are no cards in the stack. From that state, Anna repeats the following operation:

• Operation: Choose the 1st or 3rd card from the front of the row. However, if there is already a card in the stack before performing the operation, you can only choose a card from the row if at least one of its color or the integer written on it matches the top card of the stack. Remove the chosen card from the row and add it to the top of the stack.

The game ends when there are no more cards that can be chosen by the operation. The total value of the cards in the stack at the time the game ends is Anna's score.

What is the maximum score Anna can obtain in this game?

Task

Given the information about the cards lined up at the start of the game, write a program to find the maximum score Anna can obtain in this game.

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing the number of cards lined up at the start of the game.
• The following $N$ lines each contain three space-separated integers $C_i, A_i, V_i$ for the $i$-th line ($1 \le i \le N$), representing that the card at the $i$-th position from the front of the row has color $C_i$, integer $A_i$, and value $V_i$.

Output

Output the maximum score Anna can obtain in this game as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $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 1\,000\,000$ ($1 \le i \le N$).

Subtasks

Subtask 1 [10 points] * $N \le 20$ is satisfied.

Subtask 2 [15 points] * $N \le 50$ is satisfied.

Subtask 3 [75 points] * No additional constraints.

Examples

Input 1

5
1 3 2
4 2 9
1 4 6
2 3 3
2 2 1

Output 1

15

Note

Let a card with color $c$, integer $a$, and value $v$ be denoted as $(c, a, v)$. Anna can obtain the maximum score by playing the game as follows:

1. Take the 1st card from the front of the row $(1, 3, 2)$ into the stack and gain 2 points.
2. Take the 3rd card from the front of the row $(2, 3, 3)$ into the stack and gain 3 points.
3. Take the 3rd card from the front of the row $(2, 2, 1)$ into the stack and gain 1 point.
4. Take the 1st card from the front of the row $(4, 2, 9)$ into the stack and gain 9 points.

Input 2

8
11 5 31
2 8 19
2 9 2
11 8 45
4 8 22
4 2 23
6 9 58
6 2 5

Output 2

160