AT_joisc2015_i とてもたのしいカードゲーム

## JOISC2015 Day3T2 有趣的纸牌游戏 给定$N$张纸牌，纸牌自上而下堆在牌堆$A$中。牌堆$A$中从上而下第$i$张纸牌颜色是$c_i$、权值是$a_i$、价值是$v_i$。 同时你还有另一个牌堆$B$，初始$B$中没有牌。你可以进行以下操作若干次： 从牌堆中$A$选出自上而下第$1$张或者第$3$张纸牌（如果存在）。如果牌堆$B$中没有牌，或者牌堆$B$的堆顶的牌与你当前选出的牌在颜色或者权值上存在至少一个相同，则将这张纸牌移动到牌堆$B$的堆顶。 定义一个牌堆的价值为其中所有纸牌的价值之和，你需要求出牌堆$B$的可能最大价值。

第一行一个正整数$N$； 接下来$N$行每行三个正整数$c_i,a_i,v_i$表示自上而下第$i$张牌的颜色、权值、价值。

一行一个正整数表示牌堆$B$的最大可能价值。

$1 \leq N , a_i , c_i \leq 500$ $1 \leq v_i \leq 10^6$ ### 样例 #### 样例输入1 ``` 5 1 3 2 4 2 9 1 4 6 2 3 3 2 2 1 ``` #### 样例输出1 ``` 15 ``` #### 样例1解释 依次选出牌堆$A$的第$1,3,3,1$张牌可使牌堆$B$达到最大价值。 #### 样例输入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 ```