题目描述

奶牛们要去太空了！它们打算用方块建造一座太空电梯。

现在它们有 N 种方块，第 i 种方块有一个特定的高度 $h_{i}$，一定的数量 $c_{i}$。

若干个方块叠起来就可以得到一个很高的电梯，但是为了防止宇宙射线破坏方块，第 i 种方块的任何部分不能放在电梯上超过高度 $a_{i}$ 的地方。

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

输入格式

第一行，一个整数 N；

第二行到 N+1 行，第 i+1 行三个整数 $h_{i}$，$a_{i}$，$c_{i}$，数字之间用空格分隔。

输出格式

共一行，一个整数，为太空电梯的高度。

3
7 40 3
5 23 8
2 52 6

48

1
5 12 3

10

2
4 10 3
6 20 2

20

数据范围与约定

对于 100% 的数据：1≤N≤400，1≤$h_{i}$≤100，1≤$c_{i}$≤10，1≤$a_{i}$≤4×10^4。