蜗蜗家里有 $n$ 种玩偶，第 $i$ 种玩偶的大小为 $h_i$，扔掉一个玩偶的损失为 $c_i$，第 $i$ 种玩偶的数量为 $p_i$。注意，不保证 $h_i$ 互不相同。

现在蜗蜗为了家里更加美观，需要扔掉一些玩偶，使得剩下的玩偶中，最大的玩偶的数量之和严格大于扔完后剩下玩偶总数的一半，求最小损失。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含 $3$ 个整数 $h_i, c_i, p_i$。

输出格式

输出一行包含一个整数，表示答案。

样例输入 1

2
5 1 1
1 10 1

样例输出 1

1

样例输入 2

3
5 1 4
3 2 3
1 3 4

样例输出 2

9

样例3-8

见附件文件。样例 3-8 分别满足子任务 1-6 的限制。

样例解释

样例 2：

扔掉 $3$ 个第 $2$ 种玩偶，$1$ 个第 $3$ 种玩偶，损失是 $3 \times 2+1 \times 3 = 9$。

数据范围

本题采用捆绑测试。

子任务 1（10分）：$1 \leq n, h_i, c_i, p_i \leq 50$。

子任务 2（15分）：$1 \leq n, h_i, c_i, p_i \leq 500$。

子任务 3（20分）：$1 \leq n, h_i, p_i \leq 10^4$, $1 \leq c_i \leq 100$。

子任务 4（15分）：$1 \leq n, h_i, p_i \leq 10^5$, $1 \leq c_i \leq 100$。

子任务 5（20分）：$1 \leq n, h_i, c_i, p_i \leq 10^5$。

子任务 6（20分）：无特殊限制。

对于所有数据，保证 $1 \leq n, h_i, c_i, p_i \leq 5 \cdot 10^5$。