#P18119. Keep Colors Apart
Keep Colors Apart
Keep Colors Apart
有 个事件,第 个的截止日、颜色、权值分别为 ,每种颜色最多出现两次。
你可以选择任意一些事件,把它们安排到互不相同的正整数日期。事件 的安排日期不得超过 。如果相邻的两天都安排了事件,这两个事件的颜色必须不同。
允许有空日,日期本身没有额外上限;也允许一个事件都不选,此时权值为0。求所选事件权值总和的最大值。
输入格式
第一行整数 ,。
每组第一行整数 ,。接下来 行,每行三个整数 ,均在 内。
每组内每种颜色至多出现两次;所有数据的 之和不超过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天。