#AT24. Tower
Tower
[X] Tower(dp_x)
来源: AtCoder Educational DP Contest - Problem X 原题时限:2 秒 / 内存:1024 MB
题目描述
有 块积木,编号为 。对于每个 (),第 块积木的重量为 ,坚固度为 ,价值为 。
太郎要从中挑选若干块积木,按某种顺序竖直堆成一座塔。塔必须满足:
- 对于塔中任意一块积木 ,堆在它上方的所有积木的重量之和不超过 。
求塔中包含的积木价值之和的最大值。
输入格式
输入由标准输入按以下格式给出:
N
w_1 s_1 v_1
w_2 s_2 v_2
:
w_N s_N v_N
输出格式
输出价值之和的最大值。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
3
2 2 20
2 1 30
3 1 40
输出:
50
样例 2
输入:
4
1 2 10
3 1 10
2 4 10
1 6 10
输出:
40
样例 3
输入:
5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
输出:
5000000000
样例 4
输入:
8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5
输出:
22