[Usaco2005 mar]Space Elevator 太空电梯

奶牛们要进入太空！她们计划建造一座由方块堆叠而成的太空电梯，从而进入轨道。

奶牛共有 $K$ 种方块。第 $i$ 种方块的高度为 $h_i$，共有 $c_i$ 个。由于宇宙射线可能对方块造成破坏，第 $i$ 种方块的任何部分都不能超过最大高度 $a_i$。

请按照上述限制堆叠方块，求能够建造的太空电梯的最大高度。

输入格式

第一行包含一个整数 $K$，表示方块的种类数。

接下来 $K$ 行，每行包含三个以空格分隔的整数 $h_i$、$a_i$ 和 $c_i$，表示第 $i$ 种方块的高度、允许到达的最大高度以及数量。

输出格式

输出一个整数，表示能够建造的太空电梯的最大高度。

样例输入

3
7 40 3
5 23 8
2 52 6

样例输出

48

数据范围

• $1\le K\le 400$；
• $1\le h_i\le 100$；
• $1\le c_i\le 10$；
• $1\le a_i\le 4\times 10^4$。

来源与许可

本题为 USACO 2005 March 试题「太空电梯」，题面与测试数据整理自 BZOJ。

样例 1

输入

3
7 40 3
5 23 8
2 52 6

输出

48