[R36C]画廊 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有一个画廊正在进行年度展览调整。该画廊中有 $n$ 幅画作和 $n$ 个挂钩，编号都为 $1$ 到 $n$。

当前，第 $i$ 幅画作（$1 \le i \le n$）挂在编号为 $a_i$ 的挂钩上。由于陈列已久，一些挂钩上可能有多幅画作，而另一些挂钩可能是空的。

现在，画廊主管决定重新布置所有画作，最终目标是使得每个挂钩上恰好挂着一幅画。

对于每一幅画作 $i$，有以下两种操作选择：

• 原地保留：如果画廊决定让画作 $i$ 留在它原来的挂钩 $a_i$ 上，需要支付一笔保养费 $b_i$。
• 移至别处：如果画廊决定将画作 $i$ 从挂钩 $a_i$ 移走，并挂到任意一个其他的挂钩上，需要支付一笔搬运费 $c_i$。满足$b_i \leq c_i$。

求在满足最终每个挂钩上都恰有一幅画的前提下，使得总费用最小。

格式

输入格式

输入的第一行包含一个整数 $n$，表示画作和挂钩的数量。

接下来 $n$ 行，每行包含三个整数 $a_i, b_i, c_i$，分别表示第 $i$ 幅画作当前所在的挂钩编号、原地保留的保养费和移至别处的搬运费。

输出格式

输出一个整数，表示所需的最小总费用。

样例

样例输入 #1

3
1 10 100
1 20 50
2 5 10

样例输出 #1

65

数据规模

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq n$，$1 \leq b_i \leq c_i \leq 10^9$。