问题重述

奶牛们计划通过建造一个类似于太空电梯的塔来进入太空。这个塔由不同种类的块堆叠而成。有$K（1 ≤ K ≤ 400）$种不同类型的块，每种块有以下属性：

高度$h_i（1 ≤ h_i ≤ 100）$

可用数量$c_i（1 ≤ c_i ≤ 10）$

最大海拔 $a_i（1 ≤ a_i ≤ 40000）$：块的类型i的任何部分都不能超过这个海拔。

目标是堆叠这些块，使得塔的总高度$H$最大，同时满足每种块的任何部分都不超过其对应的最大海拔$a_i$。

输入数据 1

3
7 40 3
5 23 8
2 52 6

输出数据 1

48

解释：

从底部开始：$3$个类型$2$的块，上面放$3$个类型$1$的块，再上面放$6$个类型$3$的块。这样堆叠的总高度是 $35 + 37 + 6*2 = 15 + 21 + 12 = 48$。另一种堆叠方式（如$4$个类型$2$和$3$个类型$1$）是不合法的，因为最上面的类型$1$的块会超过其最大海拔$40$。