题目描述

奶牛准备去太空！他们计划建立一种太空电梯轨道：一个巨大的塔。他们有 $K$ ($1 \le K \le 400$ )种不同的砖块来建这个塔。每种砖都有一个高度 $h_i$ ( $1 \le h_i \le 100$ )、和一定的数量 $c_i$ ( $1 \le c_i \le 10$ )，为了避免宇宙射线可能引起的伤害，每种砖块都有一个最大高度限制 $a_i$ ( $1 \le a_i \le 40000$ )。

奶牛希望用这些砖块建一个尽可能高的塔。

输入格式

第一行：一个整数 $K$

接下来 $K$ 行，每行三个整数，分别表示 $h_i$, $a_i$, 和 $c_i$

输出格式

一个整数 H ，表示塔的最大高度。

样例

3
7 40 3
5 23 8
2 52 6

48

样例解释

从底部开始：第 2 种砖 3 块，第 1 种砖 3 块，第 3 种砖 6 块（ 3*5+3*7+6*2=48）。显然，堆叠 4 块的类型 2 和 3 块类型 1 是不合法的，因为最后最后一块类型1的顶部的高度为 41 ，超过了 40 。