题目描述

电工 Vasya 要焊接 $n$ 根导线。

第 $i$ 根导线连接两个接点 $a_i,b_i$，可靠性为 $r_i$，价格为 $p_i$。Vasya 可以自行决定这 $n$ 根导线的焊接顺序。

焊接过程中，已经保留下来的导线始终构成一个无环图。如果新焊接一根导线后出现了环，则环上会立刻烧掉一根导线：

1. 首先选择环上可靠性最小的导线；
2. 如果可靠性最小的导线有多根，则其中更早被焊接的那一根烧掉。

烧掉后，该导线从电路中消失，图重新变成无环图。

当所有导线都尝试焊接完后，会剩下一些没有烧掉的导线。

请计算通过适当安排焊接顺序，最终能够保留下来的导线的最大总价格。不需要输出具体焊接顺序。

输入格式

第一行一个整数 $n$：

$1\le n\le30000$。

接下来 $n$ 行，第 $i$ 行四个整数：

$a_i,b_i,r_i,p_i$。

满足：

• $1\le a_i,b_i,r_i,p_i\le10^9$；
• $a_i\ne b_i$；
• 同一对接点之间允许有多根导线。

输出格式

输出一个整数，表示最终能够得到的最大总价格。

样例

4
10 20 5 3
20 11 5 2
10 11 7 1
1 2 1 1

5