#P18119. Keep Colors Apart

Keep Colors Apart

Keep Colors Apart

有 nn 个事件,第 ii 个的截止日、颜色、权值分别为 di,ci,wid_i,c_i,w_i,每种颜色最多出现两次。

你可以选择任意一些事件,把它们安排到互不相同的正整数日期。事件 ii 的安排日期不得超过 did_i。如果相邻的两天都安排了事件,这两个事件的颜色必须不同。

允许有空日,日期本身没有额外上限;也允许一个事件都不选,此时权值为0。求所选事件权值总和的最大值。

输入格式

第一行整数 TT,1≤T≤10001\le T\le1000。

每组第一行整数 nn,1≤n≤2000001\le n\le200000。接下来 nn 行,每行三个整数 di,ci,wid_i,c_i,w_i,均在 [1,109][1,10^9] 内。

每组内每种颜色至多出现两次;所有数据的 nn 之和不超过200000。

输出格式

每组输出一行最大权值总和。

样例

5
2
1 1 100
2 1 99
2
2 1 16
3 1 4
4
2 1 37
1 2 37
2 2 12
1 1 60
7
4 3 13
2 3 3
1 1 28
6 2 30
4 1 16
5 2 21
3 4 37
10
6 3 27
5 4 8
3 5 27
2 2 11
1 5 6
1 1 33
6 3 28
1 4 32
6 2 21
2 1 30
100
20
74
132
165

第一组两个同色事件只能安排在第1、2天,无法同时选取。第二组可安排在第1、3天,以空日隔开同色事件。第三组选事件1、2,分别安排在第2、1天。第四组可按事件3、4、7、5、6安排在第1至5天;第五组可按事件8、10、3、1、9、7安排在第1至6天。