Description

现有N种箱子，每种箱子高度H_i，数量C_i。现选取若干箱子堆成一列，且第i种箱子不能放在高度超过A_i的地方。试求最大叠放高度。

Input Format

第一行，一个整数，表示箱子种类N。 接下来N行，每行三个整数，表示H_i，A_i，C_i。

Output Format

一个整数，表示最大高度。

3
7 40 3
5 23 8
2 52 6

48

Hint

N  < =  400  ,  H_i  < =  100  ,  C_i  < =  10  ,  A_i  < =  40000

Source

动态规划