题目描述

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

输入格式

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

输出格式

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

样例 1

输入

3
7 40 3
5 23 8
2 52 6

输出

48

提示

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

---

题目来源：Vivian  Snow；FPS 共享题包，题包内第 11 题。保留原作者与原赛事署名。