17724번 - Card Game Is Great Fun 서브태스크다국어

アンナは友人のブルーノとよくカードゲームで遊んでいたが，2 人で行うゲームには飽きてしまったの で 1 人でできるカードゲームを考えた．

このゲームの開始時には，さまざまな色のカードが N 枚一列に並んでおり，それぞれのカードには整数 が 1 つ書かれている．それぞれのカードの色は整数で表される．また，それぞれのカードには価値が定まっ ている．ゲーム開始時に列の先頭から i 番目 (1 ≦ i ≦ N) にあるカードの色は C_i であり，書かれている整 数は A_i である．そのカードの価値は V_i である．

カードの列からカードを 1 枚選んで取り除き，山札に加えていくという操作を繰り返すことでゲームを 行う．はじめ，山札にカードはなく，その状態からアンナは以下の操作を繰り返す．

• 操作：カードの列の先頭から 1 番目もしくは 3 番目のカードを選ぶ．ただし，操作を行う前に山札 にカードが存在するときには，山札の一番上のカードと，色または書かれている整数の少なくとも一 方が一致しているようなカードしか列から選ぶことができない．選んだカードを列から取り除いて， 山札の一番上に加える．

操作によって選ぶことのできるカードが無くなった時点でゲームは終了する．ゲームが終了した時点で 山札にあるカードの価値の合計がアンナの得点となる．

このゲームにおいてアンナが得ることのできる得点の最大値はいくらになるだろうか．

ゲーム開始時に並んでいるカードの情報が与えられたとき，このゲームにおいてアンナが得ることので きる得点の最大値を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N が書かれている．これは，ゲーム開始時にカードが N 枚並んでいることを表す．
• 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には， 3 個の整数 C_i, A_i, V_i が空白を区切りとして書かれてい る．これは，ゲーム開始時に列の先頭から i 番目にあるカードの色が C_i，書かれている整数が A_i，価 値が V_i であることを表す．

標準出力に，このゲームにおいてアンナが得ることのできる得点の最大値を表す整数を 1 行で出力せよ．

• 1 ≦ N ≦ 500．
• 1 ≦ C_i ≦ 500 (1 ≦ i ≦ N)．
• 1 ≦ A_i ≦ 500 (1 ≦ i ≦ N)．
• 1 ≦ V_i ≦ 1 000 000 (1 ≦ i ≦ N)．