/
実行時間制限: 3 sec / メモリ制限: 1250 MiB
配点 : 100 点
問題文
アンナは友人のブルーノとよくカードゲームで遊んでいたが,2 人で行うゲームには飽きてしまったので 1 人でできるカードゲームを考えた.
このゲームの開始時には,さまざまな色のカードが N 枚一列に並んでおり,それぞれのカードには整数が 1 つ書かれている.それぞれのカードの色は整数で表される.また,それぞれのカードには価値が定まっている.ゲーム開始時に列の先頭から i 番目 (1 \leqq i \leqq N) にあるカードの色は C_{i} であり,書かれている整数は A_{i} である.そのカードの価値は V_{i} である.
カードの列からカードを 1 枚選んで取り除き,山札に加えていくという操作を繰り返すことでゲームを行う.はじめ,山札にカードはなく,その状態からアンナは以下の操作を繰り返す.
- 操作:カードの列の先頭から 1 番目もしくは 3 番目のカードを選ぶ.ただし,操作を行う前に山札にカードが存在するときには,山札の一番上のカードと,色または書かれている整数の少なくとも一方が一致しているようなカードしか列から選ぶことができない.選んだカードを列から取り除いて,山札の一番上に加える.
操作によって選ぶことのできるカードが無くなった時点でゲームは終了する.ゲームが終了した時点で山札にあるカードの価値の合計がアンナの得点となる.
このゲームにおいてアンナが得ることのできる得点の最大値はいくらになるだろうか.
課題
ゲーム開始時に並んでいるカードの情報が与えられたとき,このゲームにおいてアンナが得ることのできる得点の最大値を求めるプログラムを作成せよ.
入力
標準入力から以下のデータを読み込め.
- 1 行目には,整数 N が書かれている.これは,ゲーム開始時にカードが N 枚並んでいることを表す.
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には,3 個の整数 C_{i}, A_{i}, V_{i} が空白を区切りとして書かれている.これは,ゲーム開始時に列の先頭から i 番目にあるカードの色が C_{i},書かれている整数が A_{i},価値が V_{i} であることを表す.
出力
標準出力に,このゲームにおいてアンナが得ることのできる得点の最大値を表す整数を 1 行で出力せよ.
制約
すべての入力データは以下の条件を満たす.
- 1 \leqq N \leqq 500.
- 1 \leqq C_{i} \leqq 500 (1 \leqq i \leqq N).
- 1 \leqq A_{i} \leqq 500 (1 \leqq i \leqq N).
- 1 \leqq V_{i} \leqq 1\,000\,000 (1 \leqq i \leqq N).
小課題
小課題 1 [10 点]
- N \leqq 20 を満たす.
小課題 2 [15 点]
- N \leqq 50 を満たす.
小課題 3 [75 点]
追加の制限はない.
入力例 1
5 1 3 2 4 2 9 1 4 6 2 3 3 2 2 1
出力例 1
15
色が c,書かれている整数が a,価値が v であるカードを (c, a, v) と表す.
次のようにゲームを行うことで,アンナは最大の得点を得ることができる.
- 列の先頭から 1 番目にあるカード (1, 3, 2) を山札にとり 2 点を得る.
- 列の先頭から 3 番目にあるカード (2, 3, 3) を山札にとり 3 点を得る.
- 列の先頭から 3 番目にあるカード (2, 2, 1) を山札にとり 1 点を得る.
- 列の先頭から 1 番目にあるカード (4, 2, 9) を山札にとり 9 点を得る.
入力例 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
出力例 2
160