该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在云雾缭绕的魔法大陆深处，矗立着一座古老的星界塔，传说塔顶连接着星辰的奥秘。年轻的巫师学徒艾德里安决心用他收集的魔法石重新修缮这座塔，使其直通星界。他手中有 $N$ 种珍稀的魔法石，每种石头都蕴含着不同的星界能量，唯有遵循它们的能量规则，才能让塔楼稳固地升入天际。

每一种魔法石都有三个神秘属性：

• 高度 $h_i$：每块该魔法石能为塔楼增加的高度，是构建塔楼的基础单位；
• 能量阈值 $a_i$：该魔法石在塔楼中允许出现的最高位置——即从塔底到该石头所在层的总高度不能超过 $a_i$，否则石头会因能量过载而碎裂；
• 储量 $c_i$：艾德里安手中拥有的该魔法石数量，每使用一块，储量便减少一。

艾德里安的目标是利用这些魔法石，搭建出尽可能高的星界塔。每一块魔法石的放置都必须满足：从塔底到其所在层的总高度不超过它的能量阈值。请你帮助这位年轻的巫师，计算星界塔能够达到的最大高度。

输入格式

• 第一行是一个整数 $N$，代表魔法石的种类数。
• 接下来 $N$ 行，每行包含三个整数 $h_i$、$a_i$、$c_i$，分别表示第 $i$ 种魔法石的高度、能量阈值和储量。

输出格式

一行整数，即星界塔能够达到的最高高度。

输入输出样例 #1

输入 #1

3  
7 40 3  
5 23 8  
2 52 6  

输出 #1

48  

说明/提示

对于10%的数据，$N = 1$。

对于另外40%的数据，$N = 2$

对于 $100\%$ 的数据：$1\le N\le 400$，$1\le h_i \le 100$，$1\le c_i\le 10$，$1\le a_i\le 4\times 10^4$。

样例解释

1. 先使用第二种魔法石，因为其能量阈值相对较低。使用 4 块第二种魔法石，此时塔的高度为 $5\times4 = 20$，没有超过其能量阈值 23。
2. 接着使用第一种魔法石，使用 4 块第一种魔法石。由于之前塔高为 20，使用第一块第一种魔法石后塔高变为 $20 + 7=27$，使用 4 块后塔高为 $20+7\times4 = 48$，也没有超过第一种魔法石的能量阈值 40。
3. 若再尝试使用其他魔法石，无论使用哪种都会违反能量阈值的限制。例如，若再使用一块第一种魔法石，塔高变为 $48 + 7 = 55$，超过了其能量阈值 40；若使用第三种魔法石，虽然其能量阈值 52 大于 48，但找不到其他更优的组合能使塔继续增高。

所以，通过这样的合理安排，星界塔能够达到的最大高度就是 48。