카드 게임은 정말 재밌다

안나는 친구 브루노와 카드 게임을 자주 했지만, 둘이 하는 게임에는 싫증이 나서 혼자 할 수 있는 카드 게임을 만들었다.

게임을 시작할 때 색이 다양한 카드 $N$장이 한 줄로 놓여 있고, 각 카드에는 정수가 하나씩 적혀 있다. 카드의 색도 정수로 나타내며, 각 카드에는 가치가 정해져 있다. 시작할 때 앞에서 $i$번째 ($1 \le i \le N$) 카드의 색은 $C_i$, 적힌 정수는 $A_i$, 가치는 $V_i$이다.

게임은 다음 동작을 반복하며 진행한다. 안나는 카드 열에서 카드를 한 장 골라 열에서 제거하고, 더미 맨 위에 올린다. 더미는 처음에 비어 있다.

• 동작: 카드 열의 앞에서 1번째 또는 3번째 카드를 고른다. 더미에 카드가 있으면, 더미 맨 위 카드와 색 또는 적힌 정수 중 적어도 하나가 일치하는 카드만 고를 수 있다. 고른 카드를 열에서 제거해 더미 맨 위에 올린다.

고를 수 있는 카드가 없으면 게임이 끝난다. 그때 더미에 있는 카드의 가치 합이 안나의 점수가 된다.

안나가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에 정수 $N$이 주어진다. 게임을 시작할 때 카드가 $N$장 놓여 있다는 뜻이다.
• 이어지는 $N$개 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 공백으로 구분된 정수 $C_i$, $A_i$, $V_i$가 주어진다. 앞에서 $i$번째 카드의 색이 $C_i$, 적힌 정수가 $A_i$, 가치가 $V_i$라는 뜻이다.

표준 출력에 안나가 얻을 수 있는 점수의 최댓값을 정수 하나로 한 줄에 출력한다.

• $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$)