#AT24. Tower

Tower

[X] Tower(dp_x)

来源: AtCoder Educational DP Contest - Problem X 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 块积木,编号为 1,2,…,N1, 2, \ldots, N。对于每个 ii(1≤i≤N1 \le i \le N),第 ii 块积木的重量为 wiw_i,坚固度为 sis_i,价值为 viv_i。

太郎要从中挑选若干块积木,按某种顺序竖直堆成一座塔。塔必须满足:

  • 对于塔中任意一块积木 ii,堆在它上方的所有积木的重量之和不超过 sis_i。

求塔中包含的积木价值之和的最大值。

输入格式

输入由标准输入按以下格式给出:

N
w_1 s_1 v_1
w_2 s_2 v_2
:
w_N s_N v_N

输出格式

输出价值之和的最大值。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤1031 \le N \le 10^3
  • 1≤wi,si≤1041 \le w_i, s_i \le 10^4
  • 1≤vi≤1091 \le v_i \le 10^9

样例 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