题目描述

牛们要到太空去了！他们打算建造一座太空电梯来送他们进入轨道．

有${K(1≤}$${K≤}$${400)}$神方块，第${i}$种有一个特定的高度${hi(l≤}$${hi≤}$${100)，}$一定的存量${ci(l≤}$${ci≤}$${10).}$为防宇宙射线的破坏，第${i}$种方块的任何部分不能超过高度${ai(l≤}$${ai≤}$${40000)}$．

请用这些方块堆出最高的太空电梯．

输入格式

第${1}$行输入一个整数${K.}$

接下来${K}$行，每行输入三个整数${hi，}$${ai，}$${ci}$．

输出格式

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

样例

输入样例

3
7 40 3
5 23 8
2 52 6

输出样例

48

提示

从底部开始，先放${3}$个方块${2，}$之后${3}$个方块${1，}$接下来${6}$个方块${3}$．不能把${3}$个方块${1}$堆到${4}$个方 块${2}$上，因为这样最高的方块${1}$的顶部高度超过了${40.}$