#CW35. 彩带拼接(ribbonmix)

彩带拼接(ribbonmix)

题目描述

桌面上按编号从 11 到 nn 排列着 nn 条彩带。第 ii 条彩带有三个属性:长度 lil_i、美观度 viv_i 和颜色 cic_i。

小 W 可以选择若干条彩带,但不能改变它们在桌面上的先后顺序。被选择的彩带会依次首尾相接,形成一条新彩带;相邻两条被选彩带的颜色必须不同,第一条彩带没有前一条,因此不受颜色限制。选择的总长度必须恰好等于 LL,目标是让总美观度尽可能大。若不存在满足条件的选择,输出 −1-1。

输入格式

第一行两个整数 n,Ln,L(1≤n≤10001 \le n \le 1000,1≤L≤1051 \le L \le 10^5)。

接下来 nn 行每行三个正整数 li,vi,cil_i,v_i,c_i,满足 li≤105l_i \le 10^5、vi≤105v_i \le 10^5、ci≤109c_i \le 10^9。

输出格式

输出一个整数,表示最大总美观度;无合法选择时输出 −1-1。

样例 1 输入

3 5
2 3 1
3 5 2
2 4 1

样例 1 输出

9

样例 1 解释

选择第 1,21,2 条时总长度为 2+3=52+3=5,颜色不同,美观度为 3+5=83+5=8。选择第 2,32,3 条时总长度也是 55,颜色 2,12,1 不同,美观度为 5+4=95+4=9。其他选择不能同时满足长度和相邻颜色条件,所以答案是 99。

数据范围

1≤n≤10001 \le n \le 1000,1≤L≤1051 \le L \le 10^5,li≤105l_i \le 10^5,vi≤105v_i \le 10^5,ci≤109c_i \le 10^9。

数据类别 分值 测试点 附加条件
A 20 1∼51\sim 5 n≤20n \le 20,L≤100L \le 100
B 25 6∼96\sim 9 n≤100n \le 100,L≤500L \le 500
C 10 10∼1110\sim 11 所有颜色相同
D 15 12∼1412\sim 14 L≤1000L \le 1000
E 30 15∼2015\sim 20 无附加限制