也许你了解著名的俄罗斯纪念品——俄罗斯套娃。它看起来是一组嵌套的木制玩偶。较小尺寸的玩偶被放入较大的玩偶中。让我们考虑将所有玩偶拆开的情况。每个玩偶都有一个外体积 $out_i$（即它在空间中占用的体积）和一个内体积 $in_i$（即玩偶内部空心空间的体积）。你可以认为，如果第一个玩偶的外体积严格小于第二个玩偶的内体积，就可以将第一个玩偶放入第二个玩偶中。如果两个或多个玩偶在另一个玩偶内部，它们不能并排摆放，必须是嵌套关系。

对于每个玩偶，每单位空心空间的成本 $cost_i$ 是已知的。你必须为直接属于第 $i$ 个玩偶（但不属于其内部玩偶）的每单位空心空间支付恰好 $cost_i$ 的费用。只要不违反规则，你可以按你希望的方式排列玩偶。目标是找到一种嵌套玩偶的方案（不一定包含所有玩偶），使得你需要支付的总成本最小。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 1000$），表示你拥有的玩偶数量。

接下来的 $N$ 行中，第 $i$ 行包含三个整数 $out_i$、$in_i$、$cost_i$（$1 \le in_i < out_i \le 1000$，$1 \le cost_i \le 1000$），分别表示第 $i$ 个玩偶的外体积、内体积和单位空心空间成本。

输出格式

输出单个整数 $P$，表示你需要支付的最小可能总成本。

样例

输入样例 1

3
5 4 1
4 2 2
3 2 1

输出样例 1

7