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