题目描述
桌面上按编号从 1 到 n 排列着 n 条彩带。第 i 条彩带有三个属性:长度 li、美观度 vi 和颜色 ci。
小 W 可以选择若干条彩带,但不能改变它们在桌面上的先后顺序。被选择的彩带会依次首尾相接,形成一条新彩带;相邻两条被选彩带的颜色必须不同,第一条彩带没有前一条,因此不受颜色限制。选择的总长度必须恰好等于 L,目标是让总美观度尽可能大。若不存在满足条件的选择,输出 −1。
输入格式
第一行两个整数 n,L(1≤n≤1000,1≤L≤105)。
接下来 n 行每行三个正整数 li,vi,ci,满足 li≤105、vi≤105、ci≤109。
输出格式
输出一个整数,表示最大总美观度;无合法选择时输出 −1。
样例 1 输入
3 5
2 3 1
3 5 2
2 4 1
样例 1 输出
9
样例 1 解释
选择第 1,2 条时总长度为 2+3=5,颜色不同,美观度为 3+5=8。选择第 2,3 条时总长度也是 5,颜色 2,1 不同,美观度为 5+4=9。其他选择不能同时满足长度和相邻颜色条件,所以答案是 9。
数据范围
1≤n≤1000,1≤L≤105,li≤105,vi≤105,ci≤109。
| 数据类别 |
分值 |
测试点 |
附加条件 |
| A |
20 |
1∼5 |
n≤20,L≤100 |
| B |
25 |
6∼9 |
n≤100,L≤500 |
| C |
10 |
10∼11 |
所有颜色相同 |
| D |
15 |
12∼14 |
L≤1000 |
| E |
30 |
15∼20 |
无附加限制 |