当前没有测试数据。

题目描述

The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village. There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor. There are n kinds of trees. The number of i-th kind of trees is P_iP i ​ , the height of i-th kind of trees is H_iH i ​ , the cost of cutting down one i-th kind of trees is C_iC i ​ .

(Note: "cutting down a tree" means removing the tree from the forest, you can not cut the tree into another height.)

输入格式

The problem is multiple inputs (no more than 30 groups). For each test case. The first line contines one positive integers $(1 \leq n \leq 10^5)$(1≤n≤10 5 ),the kinds of trees. Then followed n lines with each line three integers $(1 \leq H_i \leq 10^9)$ ​ (1≤H i ​ ≤10 9 )-the height of each tree, $(1 \leq C_i \leq 200)$ ​ (1≤C i ​ ≤200)-the cost of cutting down each tree, and $(1 \leq P_i\leq 10^9)$ ​ (1≤P i ​ ≤10 9 )-the number of the tree.

输出格式

For each test case, you should output the minimum cost.

样例

样例输入 1

2
5 1 1
1 10 1
2
5 1 2
3 2 3

样例输出 1

1
2