站外题求助

有 n 个箱子，编号为 1∼n。第 i 号箱子的高度是hi，重量为 wi，承重能力是 si。 现在要从这n个箱子中选若干个，按照任意顺序纵向叠成一个塔。要求每个箱子上面的箱子的总重量，不能超过自身的承重能力。

【输入格式】 第 1 行，1 个正整数 n。

第 2∼n+1 行，每行 3 个正整数 wi,si,hi。

【输出格式】 输出能叠出的最大高度。

input

3

2 2 20

2 1 30

3 1 40

output

50

input

5 2 4 900000000

2 7 400000000

2 4 300000000

2 2 1000000000

2 6 100000000

output

2600000000