#101739. [BZOJ 1739] [Usaco2005 mar]Space Elevator 太空电梯

The cows are going to space! They plan to achieve orbit by building a sort of space elevator:
a giant tower of blocks. They have different types of blocks with which to build the tower. Each block of type has height and is available in quantity . Due to possible damage caused by cosmic rays, no part of a block of type can exceed a maximum altitude . Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

牛们要到太空去了！他们打算建造一座太空电梯来送他们进入轨道。
有 种方块，第 种有一个特定的高度 ，一定的存量 . 为防宇宙射线的破坏，第 种方块的任何部分不能超过高度 。请用这些方块堆出最高的太空电梯。

• Line : A single integer, .
• Lines : Each line contains three space-separated integers: , and . Line describes block type .
• 第一行输入一个整数 。
• 接下来 行，每行输入三个整数 。

• Line : A single integer , the maximum height of a tower that can be built.
• 一个整数，表示最大高度。

样例输入 #1

3
7 40 3
5 23 8
2 52 6

样例输出 #1

48

样例说明

从底部开始，先放 个方块 ，之后 个方块 ，接下来 个方块 。不能把 个方块 堆到 个方块 上，因为这样最高的方块 的顶部高度超过了 。

对于 的数据，，，，。 Gold