题目描述

懒散的 Bob 偶然发现了一台自动售货机。在观察了足够多的人购买美味零食之后，Bob 意识到这台售货机坏了！

懒散的 Bob 观察到以下情况：

1. 一个人试图购买一种零食
2. 自动售货机检查该零食是否还有剩余
3. 如果有剩余，机器会向该人收取该零食的费用
4. 如果机器成功收费，它会给该人一个 不同 的零食！如果那种不同的零食已经售罄，则可能什么都不给！

懒散的 Bob 注意到，尽管机器坏了，但至少它是一致的。每当顾客从位置 $i$ 购买零食时，机器从位置 $f(i)$ 出货，其中 $f$ 是某个可预测的函数。

现在，Bob 想从这台机器中获利。他想从机器中购买一些零食，然后将得到的零食按市场价转卖。这个市场价可能与购买价不同。如果一个便宜零食在 $i$ 位置，而一个昂贵零食在 $f(i)$ 位置，他就能大赚一笔！假设 Bob 总能找到买家，请问 Bob 通过购买一定数量（可能为零）的零食然后转卖，能获得的最大净收益是多少？你可以假设 Bob 通过其他不正当手段有足够的资金来支付从自动售货机购买任意数量零食的费用。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入的第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$），表示机器中零食位置的数量。接下来的 $n$ 行，每行包含 4 个空格分隔的整数 $f$、$p$、$m$、$s$，按顺序从 $1$ 到 $n$ 描述机器中的一个零食位置，其中：

• $f$（$1 \leq f \leq n$）是 $f(i)$ 的值，即当 Bob 从该位置购买时，机器出货的位置
• $p$（$1 \leq p \leq 1\,000\,000$）是 Bob 从该位置购买所需支付的价格
• $m$（$1 \leq m \leq 1\,000\,000$）是该位置零食的市场价格
• $s$（$1 \leq s \leq 1\,000\,000$）是该位置零食的数量

输出格式

输出一行一个整数，表示懒散的 Bob 通过恶意滥用这台坏掉的自动售货机所能获得的最大利润。

3
1 2 3 1
2 3 4 1
3 4 5 1

3

3
2 2 3 8
3 1 5 6
1 9 4 7

39

5
5 9 2 2
1 1 7 4
2 3 6 3
2 2 9 6
1 4 5 1

22

提示

翻译由 DeepSeek V3.2 完成